LeetCode 31. 下一个排列(Next Permutation)

时间:2022-12-15 11:26:20

题目描述

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。

必须原地修改,只允许使用额外常数空间。

以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,31,3,2
3,2,11,2,3
1,1,51,5,1

解题思路

由于各个排列按照字典序排序,所以以 1,3,2 → 2,1,3为例,寻找下一个排列的步骤是:

  • 首先找到从后往前第一个升序数对,在此例中即(1,3)
  • 然后在升序对前一个数后面的数组中,从后往前找到第一个比升序对前一个数大的数,并将其与升序对前一个数交换,在此例中即找到2比1大,所以将2与1交换得到2,3,1
  • 最后将交换后的数组从升序对后一个数开始按升序排序,在此例中即从3开始按升序排序得到2,1,3

在第一步中,若遍历到数组头部仍未找到升序对,说明不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。

代码

 class Solution {
public:
void nextPermutation(vector<int>& nums) {
for(int i = nums.size() - ; i >= ; i--){
if(i == )
sort(nums.begin(), nums.end());
else if(nums[i] > nums[i - ]){
int minIdx = nums.size() - ;
while(nums[i - ] >= nums[minIdx])
minIdx--;
swap(nums[minIdx], nums[i - ]);
sort(nums.begin() + i, nums.end());
break;
}
}
}
};