楼主:
JIWP (JIWP)
2025-01-25 11:41:572948. 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
}