2024-03-16：用go语言，给你一个正整数数组 nums，
每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。
（注意，在后续操作中你可以对减半过的数继续执行操作）
请你返回将 nums 数组和 至少 减少一半的 最少 操作数。
输入：nums = [5,19,8,1]。
输出：3。
答案2024-03-16：
来自左程云。
大体步骤如下：
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)
