Share my clean short O(n) solution with comments and example


  • 2
    U

    class Solution {

    public:

    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 1;
        while(i > 0) {
           if (nums[i] > nums[i-1]) { /* search the first element from the back that is not in descending order, which is nums[i-1] */
               int j = nums.size()-1;
               while(nums[i-1] >= nums[j]) j--; /* search the first element from the back in the range (nums[i], nums[nums.size()-1] that is larger than num[i-1] */
               swap(nums[i-1], nums[j]); /* swap the two elements we just found */
               break;
           }
           i--;
        }
        reverse(nums.begin()+i, nums.end()); /* this range should be in increasing order */
    }
    

    };

    Let's look at an example:

    [5, 8, 21, 15, 10, 6]

    first, find 8;

    then, find 10 from [21, 15, 10, 6] that is larger than 8 and is closest to the end;

    swap, to [5, 10, 21, 15, 8, 6];

    finally, the range [21, 15, 8, 6] needs to be in increasing order as [6, 8, 15, 21], we got [5, 10, 6, 8, 15, 21].


  • 0
    G

    Awesome explanation. Thanks


Log in to reply
 

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