2024-03-16：用 go 语言，给你一个正整数数组 nums，每一次操作中，你可以从 nums 中选择任意一个数并将它减小到恰好一半。（注意，在后续操作中你可以对减半过的数继续执行操作）

作者：福大大架构师每日一题

2024-03-16
北京
本文字数：1154 字
阅读完需：约 4 分钟

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)