问题描述
考虑一组数字 123，其排列组合共有六种：123, 132, 213, 231, 312, 321。这些排列组合是根据 < 比较符按数值排序。在这六种排列组合中，123 排第一位，没有上一个排列；321 排最后一位，没有下一个排列。除此之外任意一个排列组合都有上一个排列和下一个排列，比如 231 的上一个排列是 213，下一个排列是 312。
注：当然也可以循环定义下一个排列，尾排列的下一个排列是首排列。
现在以数组 nums 的形式给出一个排列，要求原地修改得到其下一个排列，若没有下一个排列则无需改动。
算法描述
核心思想是贪心。一个重要的事实是下一个排列应该比当前序列大，但是差距要最小。
从权重的角度出发，越靠右的数字代表的权重越小。
-
为了尽可能缩小差距，根据事实，从右往左遍历数字，当首次遇见相邻两个数字构成升序对时，靠左的数字成为交换点，以 123654 为例，3 和 6 构成升序对，3 成为交换点。
-
哪个数字与交换点进行交换呢？为了缩小差距，应该用交换点后面所有数字中最小的、又比交换点大的那个数和它交换。在这里是 6, 5, 4 中的 4，得到 124653。
-
最后将交换点之后的数字升序，得到 124356 即为答案（其实将交换点之后的数字反转就可以了，注意到在第一步中，我们找的是首次升序对，那么就意味着交换点之后的所有数字都是降序的，而第二步的交换不会破坏这一性质）。
-
特别地，找不到交换点意味着所有数字降序，已经是最大的排列，它没有下一个排列（如果按循环排列定义，它的下一个排列是首排列，直接反转所有数字即可）。
代码实现
以 LeetCode 原题链接：下一个排列 为例，代码实现如下：
class Solution {
public:
void nextPermutation(vector<int>& nums) {
const int n = nums.size();
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) { --i; } // 寻找升序对
if (i >= 0) { // 存在一对升序对
int j = n - 1;
while (nums[i] >= nums[j]) { --j; } // 寻找与交换点进行交换的那个数
swap(nums[i], nums[j]);
}
// 这个反转可以包含所有特例
// 包括 nums 只有 0 个或 1 个数
// 和 nums 已经是最大排列
reverse(nums.begin() + i + 1, nums.end());
}
};
算法分析
设 nums 的长度为 n，则：
- 时间复杂度为 \(O(n)\)。最差情况是
nums是最小排列，需要完整遍历两次。 - 空间复杂度为 \(O(1)\)。只需要几个临时变量。