Re: [閒聊] 每日leetcode
今天的每日不會寫
換一題
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
→
10/07 21:04,
1年前
, 1F
10/07 21:04, 1F
推
10/07 21:04,
1年前
, 2F
10/07 21:04, 2F
→
10/07 21:04,
1年前
, 3F
10/07 21:04, 3F
推
10/07 21:05,
1年前
, 4F
10/07 21:05, 4F
→
10/07 21:08,
1年前
, 5F
10/07 21:08, 5F
討論串 (同標題文章)
完整討論串 (本文為第 959 之 1548 篇)：