31. Next Permutation

https://leetcode.com/problems/next-permutation/description/

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

Thoughts

下一个premutation比当前的大最小的那个，假定最后结果是fir之前的不用变，它应该被替换成它之后第一个比它大的数，然后它后面的数再从小到大排列。那这个fir就是从后面找到的第一个存在后面有比它大的数。具体实现方法为从后面找从尾往头遍历, 把第一个不满足升序的两个数的位置记下来. 再从尾往头遍历, 把第一个比nums[i]大的数和nums[i] swap一下. 这时i之后都是降序的, 再把它们反过来变成升序的即可。

example: 6，3，4，9，8，7，1 此时 first ＝ 4，second = 9 从尾巴到前找到第一个大于first的数字，就是7 交换4和7，即上面的swap函数，此时序列变成6，3，7，9，8，4，1 再将second＝9以及以后的序列重新排序，让其从小到大排序，使得整体最小，即reverse一下（因为此时肯定是递减序列） 得到最终的结果：6，3，7，1，4，8，9

Code

/*
 * @lc app=leetcode id=31 lang=cpp
 *
 * [31] Next Permutation
 */

// @lc code=start
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        const int N = nums.size();
        int i = N - 2;
        for (; i >= 0 && nums[i] >= nums[i + 1]; --i) continue;
        if (i >= 0) {
            for (int j = N - 1; j > i; --j) {
                if (nums[j] <= nums[i]) continue;
                swap(nums[i], nums[j]);
                break;
            }
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};
// @lc code=end

Analysis

时间复杂度O(N), 空间O(1).