下一个排列

题目描述

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]

整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2]
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2]
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

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

数据样例

示例 1

1 2	输入：nums = [1,2,3] 输出：[1,3,2]

示例 2

1 2	输入：nums = [3,2,1] 输出：[1,2,3]

示例 3

1 2	输入：nums = [1,1,5] 输出：[1,5,1]

提示：

$1 \leq nums.length \leq 100$
$0 \leq nums[i] \leq 100$

字典序，模拟 - $O(N)$

字典序

题目所给的数字序列的字典序可以定义为：对于两个序列 $a_1, a_2, …, a_n$ 与 $b_1, b_2, …, b_m$ 而言：

$a, b$ 字典序相等：
- $n = m \vee \forall i \in [1, n], a_i = b_i$
$a$ 字典序比 $b$ 大：
- $n > m \vee \forall i \in [1, n], a_i = b_i$
- $\exists i \in [1, n], a_i > b_i \vee \forall j \in [1, i), a_i = b_i$

题目的含义是让我们寻找一个比当前给定的排列的下一个排列，整数数组的 下一个排列 是指其整数的下一个字典序更大的排列：也就是说下一个排列是比当前排列字典序大的排列中字典序最小的。

模拟

首先我们知道：

对于一个排列而言，如果我们将排列中的任何一个值替换为排在其后面的更大的一个值，那么字典序会变大。
并不是所有的位置均可以替换，下图中 6 是无法替换的

因此如果为了替换后的字典序最小，我们根据上述字典序的定义可知:

需要 尽可能的将替换的位置靠后（右）
替换后的值要尽可能的小：也就是选择替换位置右侧比其大的所有值中最小的值进行替换

因此，替换步骤 如下：

首先从后往前寻找到第一个可以替换的位置，记为 pos（保证了替换位置尽可能靠后）
从当前位置往后到结尾，寻找比当前值大的所有值中最小的值（保证了替换后的值尽可能的小）
将两个值交换（不使用额外的空间）
最后将 pos + 1 到序列结尾的序列按照升序排列（保证替换后的序列是下一个排列）

最后，剩余 若干问题需要解决：

如何判断当前位置是否可以替换呢？
是否需要最后将尾部序列进行排列？

首先，我们观察发现，当我们找到第一个可以替换的位置的时候，如下图中的 pos，那么必然后面的序列是按照 降序排列

由于降序排列，因此我们只需要找到第一个位置 $pos$ 满足：$arr[pos] < arr[pos + 1]$ 即可
遍历后面的序列找到要替换的值（比当前 $arr[pos]$ 大的最小的值）
- 由于降序排列，因此可以直接从结尾位置开始找到第一个大于 $arr[pos]$ 的位置即可
后面序列可以不进行排序，直接翻转后面序列即可变成升序序列。由于下述两个原因，使得替换后，后面的序列依然是降序序列（这里如果无法理解评论就好✨）
- 由于序列为全排列，因此后面序列中不存在和 $arr[pos]$ 相等的数
- 我们替换掉的是比 $arr[pos]$ 大的数中最小的数

时间复杂度 - $O(N)$

寻找可以替换的位置，需要遍历序列：$O(N)$
遍历后面序列找到需要替换的值：$O(N)$
替换后翻转序列：$O(N)$

因此整体时间复杂度为：$O(N)$

代码

func nextPermutation(nums []int)  {
    n, i := len(nums), len(nums) - 2
    // 寻找可以替换的位置，也就是上图中第一个会"下降"的位置，找到的位置记为 i
    for i >= 0 && nums[i] >= nums[i + 1] { i-- }
    // 如果存在这样的位置的话，需要寻找后面序列中替换的值
    if i >= 0 {
        j := n - 1
        // 从后往前，找到第一个比 nums[i] 大的数，位置记为 j
        for j >= 0 && nums[i] >= nums[j] { j-- }
        // 交换 nums[i], nums[j]
        nums[i], nums[j] = nums[j], nums[i]
    }
    // 将序列后面的降序部分翻转，实现升序排列
    reverse(nums[i + 1: ])
}

func reverse(nums []int) {
    for i, n := 0, len(nums); i < n / 2; i++ { 
        nums[i], nums[n - i - 1] = nums[n - i - 1], nums[i] 
    }
}

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) --i;
        if (i >= 0) {
            int j = nums.size() - 1;
            while (j >= 0 && nums[j] <= nums[i]) --j;
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};