Leetcode 31- 下一个排列

1. 题目描述

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

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

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

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1
2
3

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

2. 思路

先手动列举一下，依次列举有3个元素和4个元素的时候。例如4个元素时候的[1,2,3,4]。我自己列举的时候大脑里是这么想的：

1.先排最小的[1，2，3，4]
2.然后[1，2，4，3]只换后两位
3.因为以1,2 打头的肯定没有了，因为4,3已经是最大的排列了，所以考虑开始换第二个数，怎么换呢？在第2个数后面找一个最小的数（即这里的3和4之间最小的那个），将之与第2个数交换（也就是2），这个时候就变成了[1，3，4，2]。但是这样肯定不行，因为还有比它小的[1，3，2，4]，所以要换下他们之间的位置。
4.然后是[1，3，4，2]

综合以上可以得出规律，求解的思路是：

先从后往前，找到第一个前面数小于后面数的下标，记为idx
1.1 如果idx=0,肯定不存在更大的排列了，将数组逆序一下
1.2 否则跳到第2步
如果idx!=1,则存在更大的排列
2.1 找到nums[idx]~nums[l-1]中大于nums[idx-1]大且最小的那个元素，将之nums[idx-1]和交换。（注意，此时nums[idx]~nums[l-1]必定是降序的）
2.2 交换后nums[idx]~nums[l-1]任然是降序的，再将nums[idx]~nums[l-1]升序排列.

再注意一下边界条件，当只有1个元素时，直接返回。

下面是官方题解提供的图片，很清晰了：

3. 代码

这次用的是python，以后慢慢开始用Java，要重新捡起Java来了。

# -*- coding: utf-8 -*-
"""
    @Author  : LiuZhian
    @Time    : 2019/10/27 0027 下午 4:09
    @Comment : 
"""

class Solution:
	def nextPermutation(self, nums) -> None:
		"""
		Do not return anything, modify nums in-place instead.
		"""
		# 从后往前，找到第一个前面数小于后面数的下标
		l = len(nums)
		if l == 1:  # 边界情况，只要一个元素，直接返回
			return
		idx = l - 1
		while nums[idx - 1] >= nums[idx] and idx >= 1:
			idx -= 1
		# 如果idx=0,肯定不存在更大的排列了，将数组逆序一下
		if idx == 0:
			j = 0
			while (j < l // 2):
				nums[j], nums[l - 1 - j] = nums[l - 1 - j], nums[j]
				j += 1
			return
		# 如果idx!=1,则存在更大的排列
		else:
			# 策略是
			# 1. 找到nums[idx]~nums[l-1]中大于nums[idx-1]大且最小的那个元素，将之nums[idx-1]和交换。
			# 注意，此时nums[idx]~nums[l-1]必定是降序的
			i = l - 1
			while i >= idx and nums[i] <= nums[idx - 1]:
				i -= 1
			nums[idx - 1], nums[i] = nums[i], nums[idx - 1]

			# 2. 交换后nums[idx]~nums[l-1]任然是降序的
			# 再将nums[idx]~nums[l-1]升序排列
			swap_times = (l - idx) // 2
			for t in range(swap_times):
				nums[idx + t], nums[l - 1 - t] = nums[l - 1 - t], nums[idx + t]

			return

Leetcode 31- 下一个排列

Next permutation

Leetcode 31- 下一个排列

1. 题目描述

2. 思路

3. 代码

FEATURED TAGS

FRIENDS