今天的每日不會寫
換一題
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