leetcode 31. 下一个排列

题解

从后往前遍历数组,找出比当前值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)
}
}