Question

字典序排序

Answer 1

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

示例：

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解题思路：


怎么解呢？

方法一：暴力法

在这种方法中，我们找出由给定数组的元素形成的列表的每个可能的排列，并找出比给定的排列更大的排列。
但是这个方法是一种非常天真的方法，因为它要求我们找出所有可能的排列

因此，这种方法根本无法通过。 所以，我们直接采用正确的方法。
复杂度分析
时间复杂度：O(n!)，可能的排列总计有 n! 个。
空间复杂度：O(n)，因为数组将用于存储排列。

方法二：一遍扫描

首先，我们观察到对于任何给定序列的降序，没有可能的下一个更大的排列。
例如，以下数组不可能有下一个排列：
[9, 5, 4, 3, 1]
此题的目的是求一组元素可以组成的所有数字中比这组元素组成的数字下一大的一组序列
1.一种特殊情况：当序列的元素递减的时候肯定是不存在比它大的序列了，像[3,2,1]组成的数字321已经是最大的了
2.当不是上面的特殊情况的时候，举个例子：
[1,3,2,4]的下一大序列是[1,3,4,2]
[1,3,4,2]的下一大序列是[1,4,2,3]
[1,4,3,2]的下一大序列是[2,1,3,4]
所以我们要从上面找到规律

从上面，我们可以发现规律，从序列的后面向前面看，如果nums[i]>nums[i-1]那么这个序列就存在下一大元素
a.当序列的最后两个元素满足nums[i]>nums[i-1],那么直接交换位置就可以了，像[1,3,2,4]-->[1,3,4,2]
b.当序列是最后两个元素之前的元素满足nums[i]>nums[i-1]，那么我们就要考虑几个问题了，像[1,3,4,2]-->[1,4,2,3]
c.在[1,3,4,2]中，从后向前遍历，3和4满足条件，交换他们之后还要对i和之后元素进行排序，不然得到的就是[1,4,3,2]
d.在[1,4,3,2]中，1和4满足条件，但是我们不能直接交换他们，我们要在i之后的序列中找一个满足大于i-1位置元素的最小元素和它交换位置