C++ clean and short solution with O(n) time complexity


  • 0
    B

    Starting from the end of array, find the first element e_1 which is less than its following element. Reverse all elements after e_1 and then find the first element (e_2) which is greater than e_1 from these reversed elements. Swap e_1 and e_2.

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

Log in to reply
 

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