→ Firstshadow: 能別用go寫ㄇ== 10/07 21:04
推 sustainer123: 今天太簡單不屑寫 剩我只會寫ez了 10/07 21:04
→ Firstshadow: 肥肥看不懂 :( 10/07 21:04
推 oin1104: 我好崇拜你 10/07 21:05
→ JIWP: 用c很難寫ㄟ 10/07 21:08
今天的每日不會寫
換一題
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-- {
if i-1 > -1 && nums[i] > nums[i-1] {
idx = i
break
}
}
if idx == 0 {
slices.Reverse(nums)
return
}
idx--
for i := n - 1; i > idx; i-- {
if nums[i] > nums[idx] {
nums[i], nums[idx] = nums[idx], nums[i]
break
}
}
slices.Sort(nums[idx+1:])
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.213.101 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728306122.A.2B2.html