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)在这里插入图片描述
- 发表于:
- 原文链接：https://page.om.qq.com/page/OjK1WuApXXxAhY4dRk-EwVmA0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
