0031. Next Permutation
======================
题目信息
--------
:题号: 0031. 下一个排列
:难度: Medium
:主题: 数组、字典序、贪心、双指针
:原题: `LeetCode 0031 `_
:重点: 从枚举全部排列,推导到定位最右可增加位置,并以最小增量重排后缀
题目重述
--------
给定整数数组 ``nums``,把它原地变换为由相同元素组成的下一个字典序排列。
比较两个等长数组时,从左向右找到第一个不同位置;该位置元素较大的数组字典序更大。若存在比当前排列更大的
排列,需要得到其中字典序最小的一个。若当前排列已经是全部排列中的最大值,则回绕到字典序最小的排列。
数组可以包含重复值,每个值的出现次数必须保持不变。算法必须直接修改 ``nums``,并且只使用 ``O(1)`` 额外
空间。数组长度位于 ``[1, 100]``,元素位于 ``[0, 100]``。
自建示例
--------
.. code-block:: text
输入:[1, 3, 5, 4, 2]
输出:[1, 4, 2, 3, 5]
位置 1 从 ``3`` 增加为后缀中最小的更大值 ``4``,其余元素按最小顺序排列。
.. code-block:: text
输入:[1, 2, 2, 3]
输出:[1, 2, 3, 2]
重复元素的数量保持不变。
.. code-block:: text
输入:[4, 3, 3, 1]
输出:[1, 3, 3, 4]
原数组已经是最大排列,因此回绕到最小排列。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
void generateUnique(
const std::vector& sorted,
std::vector& used,
std::vector& path,
std::vector>& permutations
) {
if (path.size() == sorted.size()) {
permutations.push_back(path);
return;
}
for (int index = 0; index < static_cast(sorted.size()); ++index) {
if (used[index]) {
continue;
}
if (index > 0 &&
sorted[index] == sorted[index - 1] &&
!used[index - 1]) {
continue;
}
used[index] = true;
path.push_back(sorted[index]);
generateUnique(sorted, used, path, permutations);
path.pop_back();
used[index] = false;
}
}
void enumerateAll(std::vector& nums) {
const std::vector original = nums;
std::vector sorted = nums;
std::sort(sorted.begin(), sorted.end());
std::vector> permutations;
std::vector used(sorted.size(), false);
std::vector path;
path.reserve(sorted.size());
generateUnique(sorted, used, path, permutations);
const auto current = std::lower_bound(
permutations.begin(),
permutations.end(),
original
);
nums = current + 1 == permutations.end()
? permutations.front()
: *(current + 1);
}
void transformLocally(std::vector& nums) {
int pivot = static_cast(nums.size()) - 2;
while (pivot >= 0 && nums[pivot] >= nums[pivot + 1]) {
--pivot;
}
if (pivot >= 0) {
int successor = static_cast(nums.size()) - 1;
while (nums[successor] <= nums[pivot]) {
--successor;
}
std::swap(nums[pivot], nums[successor]);
}
std::reverse(nums.begin() + pivot + 1, nums.end());
}
public:
void nextPermutation(std::vector& nums) {
transformLocally(nums);
}
};
题解
----
全排列基线
~~~~~~~~~~
最直接的方法是生成全部不同排列,按字典序找到当前数组,再取紧随其后的排列;当前数组位于末尾时回到第一项。
``enumerateAll`` 先排序元素,再按升序选择每个位置,因此叶节点天然按字典序生成。
数组可能包含重复值。若同一递归层中前一个相同值尚未使用,再选择后一个副本只会生成等价分支,所以通过
``sorted[index] == sorted[index - 1] && !used[index - 1]`` 删除重复排列。
该方法完整覆盖定义,却会生成和保存全部排列。不同排列数量最坏达到 ``n!``,而目标只需要当前排列之后的一项。
继续优化的关键是直接构造最小的更大排列。
最右变化位置
~~~~~~~~~~~~
字典序由第一个不同位置决定。要让结果只比当前排列大一点,应尽量保留更长的原前缀,也就是让首次变化位置尽量
靠右。
从右向左扫描,找到第一个满足:
.. code-block:: text
nums[pivot] < nums[pivot + 1]
的位置。``pivot`` 右侧因此是最长非递增后缀。
非递增后缀已经是这些元素能够组成的最大排列。固定 ``pivot`` 左侧前缀后,单独重排这个后缀不可能得到更大结果,
所以必须增加 ``nums[pivot]``。由于 ``pivot`` 是最右侧仍可增加的位置,选择它能够保留最长前缀。
若不存在这样的 ``pivot``,整个数组都是非递增序列,当前排列就是全局最大值。把整个数组反转为非递减序列,
即可得到全局最小排列并完成回绕。
枢轴最小增量
~~~~~~~~~~~~
找到枢轴后,需要从后缀中选一个严格大于 ``nums[pivot]`` 的值。选择相等值不会增大排列,选择更大的候选又会在
首次变化位置产生不必要的跳跃,因此必须选择后缀中最小的严格更大值。
后缀按非递增顺序排列,从数组末尾向左扫描时,第一个满足
``nums[successor] > nums[pivot]`` 的元素正是所需后继。重复值不会影响这个结论:扫描会越过所有小于或等于
枢轴的元素,停在最靠右的可用值上。
交换后,枢轴位置完成了最小幅度的增加。任何首次变化位于枢轴左侧的排列都会更大;任何在枢轴处选择更大后继的
排列也会更大。因此剩下的任务只有一个:在已经确定的新前缀下,把后缀排列到最小。
后缀最小化
~~~~~~~~~~
设枢轴旧值为 ``x``,后继值为 ``y``。原后缀非递增,并且 ``y`` 是最靠右的严格更大值,所以:
* ``y`` 左侧的后缀元素都不小于 ``y``;
* ``y`` 右侧的元素都不大于 ``x``。
交换后,``x`` 被放到 ``y`` 的旧位置,整个后缀仍保持非递增。非递增序列的反转就是非递减序列,也就是同一
批元素能够组成的最小排列。因此无需排序,只需执行:
.. code-block:: cpp
std::reverse(nums.begin() + pivot + 1, nums.end());
算法由此同时满足三层最小性:首次变化位置最靠右、枢轴增量最小、剩余后缀最小。不存在其他排列严格位于原数组
与结果之间。
状态演化
~~~~~~~~
对 ``[1, 3, 5, 4, 2]``:
.. list-table::
:header-rows: 1
* - 阶段
- 数组状态
- 结构
* - 初始
- ``[1, 3, 5, 4, 2]``
- 最长非递增后缀为 ``[5, 4, 2]``
* - 枢轴
- ``pivot = 1``,值为 ``3``
- 最右可增加位置
* - 后继
- ``successor = 3``,值为 ``4``
- 后缀中最小的严格更大值
* - 交换
- ``[1, 4, 5, 3, 2]``
- 枢轴完成最小增量
* - 反转
- ``[1, 4, 2, 3, 5]``
- 后缀变为最小排列
复杂度分析
~~~~~~~~~~
设不同排列数量为 ``P``。全排列方法生成并保存每个长度为 ``n`` 的排列,时间和空间均为 ``O(Pn)``,最坏
``P = n!``。
主方法寻找枢轴、寻找后继和反转后缀都只进行线性扫描,总时间为 ``O(n)``。除少量下标外不分配与输入规模相关的
存储,额外空间为 ``O(1)``。