LeetCode 031 Next Permutation

LeetCode

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Example 4:

Input: nums = [1]
Output: [1]

Constraints:

1 <= nums.length <= 100 0 <= nums[i] <= 100

题目大意：

下一个全排列数

解题思路：

N/A

解题步骤：

1. 找到从后往前升序的第一个非升序数，如135864的5
2. 找到从后往前比步骤1中大的数，调换，如6，变成136854
3. 后边部分按升序排列或者做reverse(更高效)

注意事项：

1. Python语法问题： reverse子列表，跟倒序遍历数组一样，要指明前后边界，前面边界值更大

Python代码：

# 135864 -> 136854 -> 136458
# 1355864 -> 1356458
# 99
def nextPermutation(self, nums: List[int]) -> None:
	to_be_swapped_index, greater_index = -1, -1
	for i in range(len(nums) - 2, -1, -1):
		if nums[i] < nums[i + 1]: # 5 < 8
			to_be_swapped_index = i # 2
			break
	if to_be_swapped_index == -1:
		nums.sort()
		return nums
	for i in range(len(nums) - 1, to_be_swapped_index, -1): #
		if nums[to_be_swapped_index] < nums[i]: # 5 < 6
			greater_index = i # 4
			break # 136854
	nums[to_be_swapped_index], nums[greater_index] = nums[greater_index], nums[to_be_swapped_index]
	# nums[to_be_swapped_index + 1:] = sorted(nums[to_be_swapped_index + 1:]) # 136458
	nums[to_be_swapped_index + 1:] = nums[:to_be_swapped_index:-1]
	return nums

算法分析：

时间复杂度为O(n)，空间复杂度O(1)