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) 

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
470
粉丝
21
喜欢
37
收藏
22
排名:457
访问:1.9 万
私信
所有博文
社区赞助商