Permutasiya Leetcode Həllindən Massiv qurun

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The Permutasiya LeetCode Həllindən Massiv qurun – “Permutasiyadan massiv qurmaq” sıfır əsaslı permutasiyanın verildiyini bildirir ədədlər, harada eyni uzunluqda massiv qurmalıyıq ans[i] = ədədlər[numlar[i]] [0,nums.length-1] diapazonunda olan hər bir i üçün.

Sıfır əsaslı permütasyon nömrə 0-dan ədədlərə qədər fərqli tam ədədlər massividir.length-1 (daxil olmaqla).

Misal:

Input:  nums = [0,2,1,5,3,4]

Output: [0,1,2,4,5,3]

Explanation:

• cavab massivi : {rəqəmlər[numlar[0]], ədədlər[numlar[1]], ədədlər[numlar[2]], ədədlər[numlar[3]], ədədlər[numlar[4]], ədədlər[numlar[ 5]]}.
• cavab = {rəqəm[0], ədəd[2], ədəd[1], ədəd[5], ədəd[3], ədəd[4]} = [0, 1, 2, 4, 5, 3]

Input:  nums = [5,0,1,2,3,4]

Output: nums = [5,0,1,2,3,4]

Explanation:

• Nəticə cavab massivi:- [5, 0, 1, 2, 3, 4].

Yanaşma

Idea:

1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir əsas riyaziyyat.
2. Biz hər bir ədədi [i]-yə dəyişəcəyik nums[i] = (köhnə dəyər)*n + yeni dəyər.
3. Köhnə dəyəri almaq istəyiriksə, köhnə dəyər = ədəd[i]/n.
4. Yeni dəyəri əldə etmək istəyiriksə, yeni dəyər = ədəd[i]%n.
5. Orijinal daxiletmə massivində təkrarlayın və hər ədədi n-ə vurun.
6. Yenə də massivdə təkrarlayın və 2-ci addımda qeyd olunan düsturlara uyğun olaraq ədədləri[i] çevirin.
7. Və eyni massivdə yeni dəyərlər saxlamaq üçün hər bir indeksdə yeni dəyərlər əldə etmək üçün 3-cü addımda qeyd olunan düsturlardan istifadə edin.

Kodu

C++ Həlli:

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        int n = nums.size();
        for(auto& x:nums){
            x *= n;
        }
        for(int i=0;i<n;i++){
            nums[i] += nums[nums[i]/n]/n;
        }
        for(auto& x:nums){
            x %= n;
        }
        return nums;
    }
};

Java Həlli:

class Solution {
    public int[] buildArray(int[] nums) {
        int n = nums.length;
        for(int i=0;i<n;i++){
            nums[i] *= n;
        }
        for(int i=0;i<n;i++){
            nums[i] += nums[nums[i]/n]/n;
        }
        for(int i=0;i<n;i++){
            nums[i] %= n;
        }
        return nums;
    }
}

Permutasiya Leetcode Həllindən Massiv Yaratmaq üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (N) çünki biz bütün giriş massivini tam olaraq bir dəfə keçirik.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki biz heç bir əlavə yerdən istifadə etmirik.

Referans: https://en.wikipedia.org/wiki/Permutation