今天的每日不会写
换一题
31. Next Permutation
给一个整数矩阵
请回传下一个permutation
next permutation就是依照字典顺序来排序的下一个
EX
1 2 3 4的next permutation就是 1 2 4 3
4 3 2 1的next permutation就是 1 2 3 4
并须in place不能用额外的内存空间
思路:
(1)先找到最大的k满足arr[k+1] > arr[k]
如果找不到,表示现在的排序是最大的字典顺序,则将整个矩阵reverse后回传
(2)从k+1开始找到最大的i满足arr[i] > arr[k]
(3)交换arr[i]和arr[k]
(4)将i+1以后的元素由小到大排序
就可以得到答案了
golang code :
func nextPermutation(nums []int) {
n := len(nums)
idx := 0
for i := n - 1; i > -1; i