→ LabMumi: 都要過年了怎麼還在卷 你要組模型 01/25 11:42
→ JIWP: 我在等我的mb命運 01/25 11:48
2948. Make Lexicographically Smallest Array by Swapping Elements
思路:
建立一個idx矩陣:idx[i]=[i]
接著把idx跟nums按照nums的大小排序
再來就是去判斷
如果nums[i]-nums[i-1]<=limit
那這兩個就是同一個group
我們就這樣紀錄每個group的start和end
接著把idx[start:end]按照大小排序
從j=start~end把ans[idx[j]]=nums[j]
這樣就好
golang code :
func lexicographicallySmallestArray(nums []int, limit int) []int {
n := len(nums)
idx, ans := make([]int, n), make([]int, n)
for i := range idx {
idx[i] = i
}
slices.SortFunc(idx, func(a, b int) int { return nums[a] - nums[b] })
slices.Sort(nums)
start := 0
for i := 1; i < n; i++ {
if nums[i]-nums[i-1] > limit {
slices.Sort(idx[start:i])
for j := start; j < i; j++ {
ans[idx[j]] = nums[j]
}
start = i
}
}
slices.Sort(idx[start:n])
for j := start; j < n; j++ {
ans[idx[j]] = nums[j]
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.38.32 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737776519.A.2E0.html