[recommend for beginners]clean C++ implementation with detailed explanation


  • -1
    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            if(nums.size()<=1)  return;
            int i=0;
            for(i=nums.size()-1; i>0; i--){
                if(nums[i]>nums[i-1]){
                    int j=nums.size()-1;
                    while(nums[j]<=nums[i-1]) j--;
                    swap(nums[i-1], nums[j]);
                    sort(nums.begin()+i, nums.end());
                    return;
                }
            }
            if(i==0){
                reverse(nums.begin(), nums.end());
                return;
            }
        }
    };

  • 0

    Here is a implementation all by myself

    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            int n=nums.size();
            if(n<=1) return;
            int i=0;
            for(i=n-1; i>=1;){
                if(nums[i-1]>=nums[i]) i--;
                else break;
            }
            
            /** corner cases **/
            if(i==0) { reverse(nums.begin(), nums.end());  return; }
            
            int index=i-1;
            while(i<=n-1){
                if(nums[index]<nums[i]) i++;
                else break;
            }
            swap(nums[index], nums[i-1]);
            sort(nums.begin()+index+1, nums.end());
        }
    };

Log in to reply
 

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