2024-03-16：用go语言，给你一个正整数数组 nums， 每一次操作中，你可以从 nums 中选择 任意 一个数并将它减

2024-03-16：用go语言，给你一个正整数数组 nums，

每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。

（注意，在后续操作中你可以对减半过的数继续执行操作）

请你返回将 nums 数组和 至少 减少一半的 最少 操作数。

输入：nums = [5,19,8,1]。

输出：3。

答案2024-03-16：

来自左程云。

灵捷3.5

大体步骤如下：

1.定义一个优先队列（PriorityQueue）来存储数组中的数字，优先级为数字的倒数。

2.计算数组中所有数字的和，并将和除以2得到目标值（sum）。

3.初始化操作次数（ans）为0，初始化当前减半的数值之和（minus）为0。

4.循环直到当前减半的数值之和（minus）大于等于目标值（sum）：

• 弹出优先队列中最大的数值（cur）。

• 将弹出的数值除以2得到新的数值（cur/2）。

• 将新的数值添加回优先队列中。

• 更新操作次数（ans）加1。

• 更新当前减半的数值之和（minus）加上新的数值（cur/2）。

5.返回操作次数（ans）作为结果。

总的时间复杂度为O(nlogn)，其中n为数组的长度。堆操作的时间复杂度为O(logn)。

总的额外空间复杂度为O(n)，需要额外的优先队列来存储数组中的数字。

Go完整代码如下：

package main

import (

"container/heap"

"fmt"

)

type PriorityQueue []float64

func (pq PriorityQueue) Len() int {

return len(pq)

}

func (pq PriorityQueue) Less(i, j int) bool {

return pq[i] > pq[j]

}

func (pq PriorityQueue) Swap(i, j int) {

pq[i], pq[j] = pq[j], pq[i]

}

func (pq *PriorityQueue) Push(x interface{}) {

item := x.(float64)

*pq = append(*pq, item)

}

func (pq *PriorityQueue) Pop() interface{} {

old := *pq

n := len(old)

item := old[n-1]

*pq = old[0 : n-1]

return item

}

func halveArray(nums []int) int {

pq := make(PriorityQueue, 0)

sum := 0.0

for _, num := range nums {

heap.Push(&pq, float64(num))

sum += float64(num)

}

sum /= 2

ans := 0

for minus := 0.0; minus < sum; ans++ {

cur := heap.Pop(&pq).(float64) / 2

minus += cur

heap.Push(&pq, cur)

}

return ans

}

func main() {

nums := []int{5, 19, 8, 1}

result := halveArray(nums)

fmt.Println(result)

}

在这里插入图片描述Python完整代码如下：

# -*-coding:utf-8-*-

import heapq

def halveArray(nums):

pq = []

sum = 0.0

for num in nums:

heapq.heappush(pq, -float(num))

sum += float(num)

sum /= 2

ans = 0

minus = 0.0

while minus < sum:

cur = -heapq.heappop(pq) / 2

minus += cur

heapq.heappush(pq, -cur)

ans += 1

return ans

nums = [5, 19, 8, 1]

result = halveArray(nums)

print(result)在这里插入图片描述