LeetCode 0031 - Next Permutation
# Hints
- 思维
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium | or |
Implement next permutation , which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
[1,2,3] → [1,3,2]
[3,2,1] → [1,2,3]
[1,1,5] → [1,5,1]
# 题意
要求实现 next_permutation
函数的功能,即给定一个序列 ,将该序列重排,得到字典序恰好比原序列大一位的新序列。如果当前序列为字典序最大,则将其重排为字典序最小。
# 题解
原题给出的样例太小,下面两个样例可以帮助我们进行思考:
[1,2,4,3] → [1,3,2,4]
[1,3,5,4,2] → [1,4,2,3,5]
为便于描述,设 的下标为 。
显然,当序列 非严格单调递减时,不存在比它字典序更大的重排序列。由此容易发现,当序列的后缀 非严格单调递减时,下标 处应当以“最小的幅度”变大。这个变化就是与后缀中的某个元素交换,且后缀 将被重排为递增序列。至于前缀 则保持不变。
也就是说,我们需要找到最靠右的一组严格递增的相邻元素,即找到最大的 满足 。这可以通过一次遍历实现。
然后,为了使下标 处以“最小的幅度”变大,我们需要将 与后缀 中最小的比 大的元素交换,再将后缀重排为递增序列即可。时间复杂度为 。
事实上,上述算法可以被优化到 。我们注意到后缀 是非严格递减的,那么我们只需要将后缀反转即可,无需对后缀进行重新排序。
但是这样需要注意相同元素的存在,例如 ,则 ,但是我们必须选中 而不是 。考虑到后缀是递减的,我们只要倒序遍历找到第一个比 大的元素,就能达成所有要求。
由于排序已经被优化,所以现在总的时间复杂度为 。
# AC代码( 解法)
class Solution {
public:
void nextPermutation(vector<int> & nums) {
// 初始化
int n = nums.size();
// 获取变化位置
int index = n - 2;
while (index >= 0 && nums[index] >= nums[index + 1]) {
index --;
}
// 特判
if (index == -1) {
sort(nums.begin(), nums.end());
return;
}
// 获取变化位置
int m = index + 1;
for (int i = index + 2; i < n; i ++) {
if (nums[index] < nums[i] && nums[m] > nums[i]) {
m = i;
}
}
// 交换
swap(nums[index], nums[m]);
// 排序
sort(nums.begin() + index + 1, nums.end());
}
};
# AC代码( 解法)
class Solution {
public:
void nextPermutation(vector<int> & nums) {
// 初始化
int n = nums.size();
// 获取变化位置
int index = n - 2;
while (index >= 0 && nums[index] >= nums[index + 1]) {
index --;
}
// 特判
if (index == -1) {
reverse(nums.begin(), nums.end());
return;
}
// 获取变化位置
for (int i = n - 1; i >= index + 1; i --) {
// 交换
if (nums[index] < nums[i]) {
swap(nums[index], nums[i]);
break;
}
}
// 反转
reverse(nums.begin() + index + 1, nums.end());
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01