LeetCode 31.NextPermutation

LeetCode 31.NextPermutation

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.

Example:

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

---

分析：

这道题比较难，解法也比较难想到，我在discuss和solution上看到的解法都是同样的原理，具体如下：
第一种做法：利用库函数next_permutation即可返回下一个排列。
第二种做法：

• 首先从数组最右边开始往前比较，这时候是一个递增序列，然后找到第一个打破这个递增序列的数，其位置记为k。
• 如若没找到，说明整个数组从左到右为递减序列，是最后一个排列，直接返回倒过来的数组即可。例如3->2->1 整个为递减序列，直接利用reverse函数返回1->2->3。
• 然后，从数组最右边开始往前遍历，与nums[k]比较，找到第一个大于nums[k]的数，并将其位置记为m。
• 接下来，将nums[k]和nums[m]换位置，利用swap函数。
• 最后从nums[k+1]开始直至数组尾部，全部颠倒过来，即是下一个排列。

代码如下：

第一种解法：利用next_permutation函数：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end());
    }
};

第二种解法：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = -1;
        for (int i = nums.size() - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                k = i;
                break;
            }
        }
        if (k == -1) {
            reverse(nums.begin(), nums.end());
            return;
        }
        int m = -1;
        for (int i = nums.size() - 1; i > k; i--) {
            if (nums[i] > nums[k]) {
                m = i;
                break;
            }
        }
        swap(nums[k], nums[m]);
        reverse(nums.begin() + k + 1, nums.end());
    }
};
int main() {
    int n;
    cin >> n;
    vector<int> nums;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        nums.push_back(t);
    }
    Solution s;
    s.nextPermutation(nums);
    for (int i = 0; i < n; i++) {
        cout << nums[i] << " ";
    }
    return 0;
}