leetcode 31. 下一个排列

题目描述

实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。

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

题解

从后往前遍历数组,找出比当前值nums[i]大的最小值所在的位置k,然后交换nums[i],nums[k],并把i之后的数进行升序排序

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func nextPermutation(nums []int)  {
n := len(nums)
min, k := math.MaxInt64, -1
for i := n-1; i >= 0; i-- {
for j := i+1; j < n; j++ {
if nums[j] > nums[i] && nums[j] < min {
min = nums[j]
k = j
}
}
if k != -1 {
nums[i], nums[k] = nums[k], nums[i]
sort.Ints(nums[i+1:])
return
}
}
if k == -1 {
sort.Ints(nums)
}
}