简介

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

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

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

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

1,2,31,3,2 3,2,11,2,3 1,1,51,5,1

解题过程

参考官方的解析

1.如果给定序列是一个降序,那么只需要反转就可以了。

图片1
图片1

2.其他情况下,我们首先从尾部向前推进,找到a[i-1] < a[i]的数,说明a[i]之后的数是降序的, 我们只需在后面排好序的数中找到它的合适位置,即a[j] > a[i-1],a[i-1] > a[j+1]的位置,把它和j位置上的数进行调换。

图片2
图片2

func nextPermutation(nums []int) {
	i := len(nums) - 2
	for i >= 0 && nums[i+1] <= nums[i] {
		i--
	}
	if i >= 0 {
		j := len(nums) - 1
		for j >= 0 && nums[j] <= nums[i] {
			j--
		}
		swap(nums, i, j)
	}
	reverse(nums, i+1)
}

func reverse(nums []int, i int) {
	for j := len(nums) - 1; i < j; i, j = i+1, j-1 {
		swap(nums, i, j)
	}
}

func swap(nums []int, i, j int) {
	tmp := nums[i]
	nums[i] = nums[j]
	nums[j] = tmp
}