Golang | Leetcode Golang题解之第462题最小操作次数使数组元素相等II
题目:
题解:
func partition(a []int, l, r int) int {
x := a[r]
i := l - 1
for j := l; j < r; j++ {
if a[j] <= x {
i++
a[i], a[j] = a[j], a[i]
}
}
a[i+1], a[r] = a[r], a[i+1]
return i + 1
}
func randomPartition(a []int, l, r int) int {
i := rand.Intn(r-l+1) + l
a[i], a[r] = a[r], a[i]
return partition(a, l, r)
}
func quickSelect(a []int, l, r, index int) int {
q := randomPartition(a, l, r)
if q == index {
return a[q]
}
if q < index {
return quickSelect(a, q+1, r, index)
}
return quickSelect(a, l, q-1, index)
}
func minMoves2(nums []int) (ans int) {
rand.Seed(time.Now().UnixNano())
x := quickSelect(nums, 0, len(nums)-1, len(nums)/2)
for _, num := range nums {
ans += abs(num - x)
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
原文地址:https://blog.csdn.net/weixin_66442839/article/details/142749893
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!