[0031] 下一个排列

• GitHub
• http://leetcode.xuezhisd.top/post/d0c03b62.html
• https://leetcode.com/problems/next-permutation
• https://leetcode-cn.com/problems/next-permutation

题目描述

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

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

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

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

Related Topics

数组

题目解析

• 本题是一道模拟题

不确定性

方法一：一次扫描法

分析

• 对于一个顺序递减的序列，下一个排列则为顺序递增
• 从个位开始向高位看，第一次出现数值减小时，则需要在这个位置上进行改变，例如4365，因为65已经是个位和十位所显示的最大的数值，所以需要改变的数应该是百位数上3
• 从上一步中查找到的位置开始，向低位看，我们应该将它和大于它且最小的数值进行交换，例如4365，应该将3和5交换
• 对于交换完后，该位置到最低位进行递增排序，确保最小

思路

• 利用i从后向前遍历，找到第一次出现值减小情况，记为num[i]
• 利用j从后向前遍历，找到比num[i]大，且最小的值，num[j]
• 交换num[i]和num[j]的位置
• 对num[i]后的所有数值进行递增排序

注意

• 有一个隐藏的规律是，因为我们在查找需要交换位置时的条件是第一次出现数值减小时，换言之，从该位置开始到最低位是一个递减的序列。在代码中，体现为在利用j查找大于它且最小的数值时，仅仅是从后向前遍历，另外有的算法在最后排序使用reverse代替sort也是基于这个规律
• nums[i] <= nums[i - 1]和nums[j] <= nums[i]中的等号是需要考虑的情况，例如序列{1,5,1}
• 对于顺序递减的序列也需要考虑

知识点

• vector的遍历
• swap和sort函数的使用

复杂度

代码

void nextPermutation(vector<int>& nums) {
	int i = nums.size() - 1;
	while (i > 0 && nums[i] <= nums[i - 1]){
		i--; 
	}
	i--;
	if (i >= 0){
		int j = nums.size() - 1;
		while (j > 0 && nums[j] <= nums[i]){
			j--;
		}
		swap(nums[i], nums[j]);
	}
	sort(nums.begin() + (i + 1), nums.end());
}

方法二：[算法名称]

分析

思路

注意

知识点

复杂度

代码

//

相关题目

• https://leetcode-cn.com/problems/permutations/
• https://leetcode-cn.com/problems/permutations-ii/