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完整代码如下:
packagemain
import(
"container/heap"
"fmt"
)
typePriorityQueue[]float64
func(pqPriorityQueue)Len()int{
returnlen(pq)
}
func(pqPriorityQueue)Less(i,jint)bool{
returnpq[i]>pq[j]
}
func(pqPriorityQueue)Swap(i,jint){
pq[i],pq[j]=pq[j],pq[i]
}
func(pq*PriorityQueue)Push(xinterface{}){
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]
returnitem
}
funchalveArray(nums[]int)int{
pq:=make(PriorityQueue,0)
sum:=0.0
for_,num:=rangenums{
heap.Push(&pq,float64(num))
sum+=float64(num)
}
sum/=2
ans:=0
forminus:=0.0;minuscur:=heap.Pop(&pq).(float64)/2
minus+=cur
heap.Push(&pq,cur)
}
returnans
}
funcmain(){
nums:=[]int{5,19,8,1}
result:=halveArray(nums)
fmt.Println(result)
}
Python完整代码如下:
#-*-coding:utf-8-*-
importheapq
defhalveArray(nums):
pq=[]
sum=0.0
fornuminnums:
heapq.heappush(pq,-float(num))
sum+=float(num)
sum/=2
ans=0
minus=0.0
whileminuscur=-heapq.heappop(pq)/2
minus+=cur
heapq.heappush(pq,-cur)
ans+=1
returnans
nums=[5,19,8,1]
result=halveArray(nums)
print(result)
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.