LeetCode-Next Permutation

https://leetcode-cn.com/problems/next-permutation

最开始没看懂题意,后面才明白是去找全排列组合的下一个。

开始的思路是先把所有全排列写出来,然后再找,不过这样子太耗费时间,而且题目中也不允许(因为空间复杂度要求为线性)。

所以只能从找规律入手。看了半天,发现找到的规律比较零散,写起来比较困难。 然后就顺手看了一下网上的解法,真香.jpg。

主要思路是两次从后往前的查找。第一次是找到第一个非逆序排列的数字,第二次是找到刚好比第一次找到的数字大的数字,然后将这两个数字交换位置。接着,将第一次找到数字后的数字重新按照逆序排列即可。

这个规律太通用了,真香。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import "sort"
func nextPermutation(nums []int) {
n:=len(nums)
i:=n-2
j:=n-1
for i>=0 && nums[i]>=nums[i+1]{
i--
}
if i>=0{
for nums[j]<=nums[i]{
j--
}
nums[i],nums[j]=nums[j],nums[i]
}
sort.Ints(nums[i+1:])
}