leetcode-031

题目

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 and use only constant extra memory.

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

分析

这道题目的意思是给出一个序列，要求给出它的下一个置换，即按照字典序比它大的最小的那个序列。如果找不到这样的置换，那么就输出最小的那个序列(即按升序排序)。in-place的意思是让我们在交换元素时不要花费过多空间，花费的额外空间只能是常量。

解法

首先要判断是否有下一个置换，这可能不太直观，但判断没有下一个置换是很容易的：当序列已经是降序时就已经是最大的序列了，当然就不存在下一个置换，此时只要将它反过来就可以得到所求序列。因此，只要序列不是降序的，那么置换就存在。

要判断序列是否是降序，可以采取从后往前遍历的方式，如果相邻的两个元素，后面那个(right)一直比前面那个(left)小，那么就是降序的。当我们找到这样两个元素:right > left时，就找到求下一个置换的突破口了，因为这意味着在left后面的那一段子序列都是降序的，已经不存在下一个置换了，即是时候把left这个位置的元素的值变大了。

找到这样的left之后我的第一个想法是把它与后面那段子序列中比它大的最小的那个元素交换位置，再把子序列排序，这样就得到了比原始序列大的最小的序列，即下一个置换。这样的确是可以得到答案的，但是这样我们就使用了排序了，复杂度就成了O(n²)，算法自然就没那么好了。

实际上，我们知道那段子序列是降序的，那么只要把它反过来就是一个升序的序列了，这样的时间复杂度是O(n)，排好序后再去找比left大的最小的那个元素，交换它们的位置就好了。

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int len = nums.size();
        if (len == 1) return;
        bool flag = false;  //是否存在下一个置换
        int index;
        for (index = len - 1; index > 0; --index) {//找left和right
            if (nums[index] > nums[index - 1]) {
                flag = true;
                break;
            }
        }
        if (flag == false) reverse(nums.begin(), nums.end());//没有下一个置换
        reverse(nums.begin() + index, nums.end());
        int small_index = -1;
        for (int i = index; i < len; ++i) {//找比left大的最小元素
            if (nums[i] > nums[index - 1]) {
                if (small_index == -1) small_index = i;
                else if (nums[i] < nums[small_index]) small_index = i;
            }
        }
        int temp = nums[small_index];
        nums[small_index] = nums[index - 1];
        nums[index - 1] = temp;
    }
};