问题

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.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解析

首先需要理解题目的意思：

rearranges 重新排列；permutation 排列；ascending order 升序

求当前排列的下一个排列：
所谓一个排列的下一个排列的意思就是 这一个排列与下一个排列之间没有其他的排列。
这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

代码实现

//rearranges 重新排列；permutation 排列；ascending order 升序
//所谓一个排列的下一个排列的意思就是 这一个排列与下一个排列之间没有其他的排列。
//这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。
// 最差时间复杂度 O(n^2) 空间复杂度 0
class Solution {
public:
    void nextPermutation(vector
   
    & nums) { if (nums.size() == 0) return; int k = nums.size()-1; int last = k; while (k) { if (nums[k-1] < nums[k]) { while (nums[k-1] >= nums[last]) { last--; //从后往前找（也可从前往后） } swap(nums[k-1], nums[last]); break; } else { k--; } } sort(nums.begin()+k, nums.end()); } private: void swap(int &a, int &b) { int t = a; a = b; b = t; } };