[Concise C++] Easy idea with clear explanation


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

    Given array : [1, 3, 2, 4, 9, 8, 7, 6, 5]

    • As you can find, the last five elements are in reverse order [1, 3, 2, 4, | 9, 8, 7, 6, 5].
    • Which means, if the given array is [9, 8, 7, 6, 5], then it is already the last permutation of these five elements, we cannot "increase" it anymore.
    • Then we should find the least significant number of the remaining array. Among the first four numbers, [1, 3, 2, 4], the least significant number is always on the last position of this array, and it's 4 (nums[3]).
    • Then this problem is reduced to find the next permutation of [4, | 9, 8, 7, 6, 5]. Because we'll never need to touch the first three numbers to get the next permutation.
    • Because 4 (nums[3]) is on the least significant position, and [9, 8, 7, 6, 5] cannot be any larger. To get the next permutation, we need to "increase" nums[3] by the smallest possible step and "decrease" the nums[4:8] to its "smallest" permutation.
    • To get the smallest "increase" on nums[3], we need to find the smallest element in [9, 8, 7, 6, 5] that is larger than nums[3]. After swapping these two number, we need to decrease nums[4:8] to the smallest, a.k.a. in the sorted order.

    The steps are:
    [1, 3, 2, 4, | 9, 8, 7, 6, 5]
    --> [1, 3, 2, |4, 9, 8, 7, 6, 5]
    --> [1, 3, 2, |4, 9, 8, 7, 6, 5]
    --> [1, 3, 2, |5, 9, 8, 7, 6, 4]
    --> [1, 3, 2, 5, |9, 8, 7, 6, 4]
    --> [1, 3, 2, 5, |4, 6, 7, 8, 9]

    Hope this post can help you :)


Log in to reply
 

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