Medium

题目描述

给你一个正整数数组 nums 。在一次操作中，你可以从 nums 中选择任意一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续减半。）

返回将 nums 的数组和 至少 减少一半所需的最少操作数。

示例 1：

输入：nums = [5,19,8,1]
输出：3
解释：初始 nums 的和为 5 + 19 + 8 + 1 = 33 。
下面是将和减少至少一半的一种方法：
选择数字 19 并减小为 9.5 。
选择数字 9.5 并减小为 4.75 。
选择数字 8 并减小为 4 。
最终数组为 [5, 4.75, 4, 1] ，和为 5 + 4.75 + 4 + 1 = 14.75 。
nums 的和减小了 33 - 14.75 = 18.25 ，减小的部分超过了初始和的一半，18.25 >= 33/2 = 16.5 。
总共执行了 3 次操作，所以返回 3 。
可以证明，要想减半 nums 的和，3 是最少操作数。

示例 2：

输入：nums = [3,8,20]
输出：3
解释：初始 nums 的和为 3 + 8 + 20 = 31 。
下面是将和减少至少一半的一种方法：
选择数字 20 并减小为 10 。
选择数字 10 并减小为 5 。
选择数字 3 并减小为 1.5 。
最终数组为 [1.5, 8, 5] ，和为 1.5 + 8 + 5 = 14.5 。
nums 的和减小了 31 - 14.5 = 16.5 ，减小的部分超过了初始和的一半，16.5 >= 31/2 = 15.5 。
总共执行了 3 次操作，所以返回 3 。
可以证明，要想减半 nums 的和，3 是最少操作数。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^7

解题思路

这道题需要我们通过最少的操作次数，使数组和减少至少一半。每次操作可以将任意一个数减半。

核心思路：贪心策略 + 最大堆

要使操作次数最少，我们应该每次都选择当前最大的数进行减半操作。这样能够最大化每次操作对总和的减少量。

具体步骤：

  1. 计算数组的初始总和，目标减少量为总和的一半
  2. 使用最大堆（优先队列）维护所有数值
  3. 重复以下操作直到减少量达到目标：
    • 取出堆顶最大值
    • 将其减半后重新加入堆中
    • 累计减少量和操作次数

时间优化： 由于涉及浮点运算，为避免精度问题，实际实现中可以直接计算减少的总量而不是维护当前总和。

这种贪心策略是最优的，因为每次选择最大值减半能够使每步操作的收益最大化。

推荐解法： 使用优先队列实现最大堆的贪心算法。

代码实现

class Solution {
public:
    int halveArray(vector<int>& nums) {
        priority_queue<double> pq;
        double total = 0;
        
        for (int num : nums) {
            pq.push(num);
            total += num;
        }
        
        double target = total / 2;
        double reduced = 0;
        int operations = 0;
        
        while (reduced < target) {
            double largest = pq.top();
            pq.pop();
            
            double half = largest / 2;
            reduced += half;
            pq.push(half);
            operations++;
        }
        
        return operations;
    }
};

class Solution:
    def halveArray(self, nums: List[int]) -> int:
        import heapq
        
        # Python's heapq is min heap, so use negative values for max heap
        heap = [-num for num in nums]
        heapq.heapify(heap)
        
        target = sum(nums) / 2
        reduced = 0
        operations = 0
        
        while reduced < target:
            largest = -heapq.heappop(heap)
            half = largest / 2
            reduced += half
            heapq.heappush(heap, -half)
            operations += 1
        
        return operations

public class Solution {
    public int HalveArray(int[] nums) {
        var pq = new PriorityQueue<double, double>(Comparer<double>.Create((x, y) => y.CompareTo(x)));
        double total = 0;
        
        foreach (int num in nums) {
            pq.Enqueue(num, num);
            total += num;
        }
        
        double target = total / 2;
        double reduced = 0;
        int operations = 0;
        
        while (reduced < target) {
            double largest = pq.Dequeue();
            double half = largest / 2;
            reduced += half;
            pq.Enqueue(half, half);
            operations++;
        }
        
        return operations;
    }
}

var halveArray = function(nums) {
    // Use array to simulate max heap
    const heap = [...nums];
    heap.sort((a, b) => b - a);
    
    const target = nums.reduce((sum, num) => sum + num, 0) / 2;
    let reduced = 0;
    let operations = 0;
    
    while (reduced < target) {
        heap.sort((a, b) => b - a); // Re-sort to maintain max heap property
        const largest = heap.shift();
        const half = largest / 2;
        reduced += half;
        heap.push(half);
        operations++;
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n log n)
空间复杂度O(n)

详细分析：

  • 时间复杂度：初始化堆需要 O(n)，最坏情况下需要进行 O(n log n) 次堆操作，每次操作时间复杂度为 O(log n)
  • 空间复杂度：需要 O(n) 的空间存储优先队列

相关题目