LeetCode 问题 31 是一道考察排列以及数组操作知识的综合性题目。最佳解法可以使用 \(O(n)\) 的时间复杂度和常数的空间复杂度解决该问题。本文给出关于该问题的详细解释。
问题描述
实现排列组合算法，给出题目提供数组中后续的排列情况。
如果没有这样的排列，则必须将所有数组重新组合为最小的那种情况，以从头开始（比如，将这些数组按照递增方式排列）。
替换操作必须就地进行且只能用到常数的额外内存空间。
示例1:
输入: nums = [1,2,3]
输出: [1,3,2]
示例2:
输入: nums = [3,2,1]
输出: [1,2,3]
示例3:
输入: nums = [1,1,5]
输出: [1,5,1]
示例4:
输入: nums = [1]
输出: [1]
约束条件:
1 <= nums.length <= 100
0 <= nums[i] <= 100参考题解
我们以 [1,2,3,4] 做排列为例：
1 2 3 4<
1 2 4< 3
1 3 2 4<
1 3 4< 2
1 4 2 3<
1 4< 3 2
2 1 3 4<
2 1 4< 3
2 3 1 4<
2 3 4< 1
2 4 1 3<
......
4 3 1 2<
4< 3 2 1
1 2 3 4我们以一种全新的视角来看待排列（Permutation）问题：排列问题依序组合这些元素，使这些元素以大端序排列时，给出的组合是递增的——也就是说，对于数字 1、2、3 的组合，越靠左的数位的权重越高，所以 213 的权重高于 132，同样地，231 的权重则高于 213。
我们来观察进行排列时，上一组数字进行交换的位置的规律。不难发现，如果我们从右向左地查看这些数值时，将最后一个递增的数字做标记，那么下一组数字的交换位置将会是这个递增数字的左侧一个位置。我们将这个倒序查看时递增的数字的下标记作 i。
我们来以 1 2 4 3 为例，不难发现 i=2，也就是对应数字 4。而在 1 2 4 3 之后的组合 1 4 2 3 中，我们注意到最后递增的数字 4 跑到了原先其左侧 2 的位置中。而在新组合 1 4 2 3 中，数字 4 后的序列 2 3 则是递增排列的。
更进一步地，我们以 2 3 4 1 到 2 4 1 3 的变化来细化这种规律。在 2 3 4 1 这组数中，i=2，对应数字 4。而我们注意到在变化后的序列中，原先 4 左侧的数字 3 则跑到了最后一位中。也就是说，在新组合后的数字保持递增排序的过程中，也要考虑到原先 i-1 位置的数字插入到新组合哪个位置的问题。至此，我们已经找到数列变化的规律了。
最优的算法的复杂度有多高呢？由于我们需要扫描两遍数组：第一遍找到递增数列的最终位置，第二遍将本身依序排列的数组反相排列，这两步操作均为线性时间复杂度。所以该算法需要 \(O(n)\) 的时间复杂度和常数项的（不需要额外空间的）空间复杂度。
解法示例
C++
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size(), k, l;
for (k = n - 2; k >= 0; k--) {
if (nums[k] < nums[k + 1]) {
break;
}
}
if (k < 0) {
reverse(nums.begin(), nums.end());
} else {
for (l = n - 1; l > k; l--) {
if (nums[l] > nums[k]) {
break;
}
}
swap(nums[k], nums[l]);
reverse(nums.begin() + k + 1, nums.end());
}
}