Sharing my easy understanding c++ code with explanation


  • 0
    E

    Let's begin with examples
    suppose we want to get the next permutation of [3,1,2], (the answer is [3,2,1])
    we first scan from the end of the sequence, in the above example, we scan from 2
    we then continue scan the sequence from right to left, and want to find the first number smaller than 2, we then find 1
    swap them, the sequence now becomes [3,2,1], it is correct.

    Then, consider the sequence [2,3,1] (the answer if [3,1,2]), if we apply the above strategy, we get [3,2,1], it is wrong, let us revisit our above strategy.
    After scanning, we get a sequence [3,2,1], we find that if we sort [2,1] in increasing order, we can get the correct answer, we edit our code and summit to leetcode, unfortunately, we get the wrong answer for the sequence [4,2,0,2,3,2] (the answer is [4,2,0,3,2,2]).

    Applying our strategy to the above sequence, we get [4,2,2,2,3,0], sort it and get [4,2,2,0,2,3], the gap between our solution and the answer is that we only check 2 (the last element), and find the first number that is smaller than it, we ignore the situation that there exist a sequence [ai,aj,ak,am] such that ai < aj,ak,am, am < aj,ak, aj<ak, this observation tells us we have to check it more than once.

    Thus, we can write the following code:

    class Solution {
    public:
    
        // quick sort
        int median3( vector<int> & v, int left, int right ){
                int mid = left + (right-left)/2;
                if(v[mid] < v[left])
                    swap(v[mid],v[left]);
                if(v[right] < v[left])
                    swap(v[right],v[left]);
                if(v[right] < v[mid])
                    swap(v[right],v[mid]);
                swap(v[right-1],v[mid]);
                return v[right-1];
        }
    
        void quickSort(vector<int> & v, int left, int right){
            if( left < right ){
                int pivot = median3(v,left,right);
                int i = left;
                int j = right-1;
                while(i<j){
                    while(i<j && v[++i] < pivot);
                    while(i<j && v[--j] > pivot);
                    if(i<j)
                        swap(v[i],v[j]);
                    else
                        break;
                }
                swap(v[i],v[right-1]);
                quickSort(v,left,i-1);
                quickSort(v,i+1,right);
            }
        }
    
        // main function
        void nextPermutation(vector<int>& nums){
            int find = 0;   // record find or not
            int prePos = INT_MIN;
            int index = -1;
            for( int i = nums.size()-1; i > 0; i-- ){
                for( int j = i-1; j >= 0; j-- ){
                    if( nums[i] > nums[j] && j > prePos){
                        find = 1;
                        prePos = j;
                        index = i;
                    }
                }
            }
            if(!find){  // not find, must be decreasing sequence, i.e. [6,5,4,3,2,1]
                for( int i = 0; i < nums.size()/2; i++ )
                    swap(nums[i],nums[nums.size()-i-1]);
                return;
            }
            swap(nums[index],nums[prePos]);
            quickSort(nums,prePos+1,nums.size()-1);
    
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.