Næste Permutation Leetcode-løsning

Systemdesign interviewspørgsmål kan være så åben, at det er for svært at kende den rigtige måde at forberede sig på. Nu er jeg i stand til at knække designrunderne fra Amazon, Microsoft og Adobe efter køb denne bog. Daglig revision af en design spørgsmål og jeg lover, at du kan knække designrunden.

Problemformulering

Næste permutation LeetCode-løsning – "Næste permutation" angiver, at givet en matrix af heltal, som er en permutation af første n naturlige tal. Vi skal finde den næste leksikografisk mindste permutation af det givne array. Udskiftningen skal være på plads og kun bruge konstant ekstra plads.

Hvis den næste leksikografisk mindste permutation ikke eksisterer for det givne input-array, returner arrayet sorteret i stigende rækkefølge.

Eksempel:

Input:  nums = [1,2,3]

Output: [1,3,2]

Forklaring:

• Næste permutationer er: [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].
• [1, 3, 2] er den leksikografisk mindste næste permutation af [1, 2, 3].

Input:  nums = [3,2,1]

Output: [1,2,3]

Forklaring:

• Da den næste leksikografisk mindste permutation af input-arrayet ikke eksisterer, returner [1, 2, 3] som svaret.

Tilgang

Ide:

1. Hovedideen til at løse dette problem er at bruge pointers.
2. Brute force-løsningen er at generere alle permutationer af det sorterede input-array. For hver genereret permutation skal du kontrollere, om denne permutation er den leksikografiske mindste næste permutation af input-arrayet eller ej. Brute Force Solution vil få en overskredet tidsfrist, da tidskompleksiteten vil være n! hvor, n er størrelsen af ​​input-arrayet.
3. Find det første indeks fra slutningen af ​​arrayet i sådan at arr[i] < arr[i+1].
4. Find derefter største indeks j, sådan at arr[j] > arr[i] og j > i.
5. Byt om arr[i] og arr[j] og vende segmentet [i+1,n-1].
6. Det resulterende array dannet ud fra ovenstående trin er den leksikografisk mindste næste permutation af input-arrayet.

Kode

Næste Permutation Leetcode C++ Løsning:

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int index = -1,n = nums.size();
        for(int i=n-2;i>=0;i--){
            if(nums[i]<nums[i+1]){
                index = i;
                break;
            }
        }
        for(int i=n-1;i>index and index!=-1;i--){
            if(nums[i]>nums[index]){
                swap(nums[i],nums[index]);
                break;
            }
        }
        reverse(nums.begin()+index+1,nums.end());
    }
};

Næste Permutation Leetcode Java-løsning:

class Solution {
    public void nextPermutation(int[] nums) {
        int index = -1,n = nums.length;
        for(int i=n-2;i>=0;i--){
            if(nums[i]<nums[i+1]){
                index = i;
                break;
            }
        }
        for(int i=n-1;i>=0 && index!=-1;i--){
            if(nums[i]>nums[index]){
                int temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
                break;
            }
        }
        int l = index + 1,r = n - 1;
        while(l<r){
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l++;r--;
        }
    }
}

Kompleksitetsanalyse for næste permutation Leetcode-løsning

Tidskompleksitet

Tidskompleksiteten af ​​ovenstående kode er PÅ) da vi i værste fald krydser hele input-arrayet én gang, hvor N = størrelsen af ​​input-arrayet.

Rumkompleksitet

Rumkompleksiteten af ​​ovenstående kode er O (1) siden vi bruger konstant ekstra plads.

Reference: https://docs.microsoft.com/en-us/cpp/standard-library/algorithm-functions?view=msvc-170