LeetCode 31. 下一个排列
题目类型
- 数组
- 找规律题
题目链接
思路
建议画图用例子模拟
[2 3 5 4 1] => [2 4 1 3 5]
- 先用指针k从后往前找,找到第一个不满足nums[k - 1]>nums[k]的位置,即k即往后的都为降序
- 如果k在nums起始位置,则将整个数组反转,否则执行3
- 用指针t从指针k所在位置往右寻找,找到第一个大于nums[k-1]的数,此时整个数为nums[t - 1]
- 并且将nums[k-1]和nums[t - 1]互换
- 将k后面的序列反转
AC代码
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int k = nums.size() - 1;
// 2 3 5 4 1
// 此时处于5这个位置
while (k > 0 && nums[k - 1] >= nums[k]) k --;
// 整个序列都是降序
if (k <= 0)
{
reverse(nums.begin(), nums.end());
}
else
{
int t = k;
while (t <= nums.size() - 1 && nums[t] > nums[k - 1]) t ++;
swap(nums[k - 1], nums[t - 1]);
reverse(nums.begin() + k, nums.end());
}
}
};