2208. 将数组和减半的最少操作次数

🎯 问题描述（来源于LeetCode）

描述：
给你一个正整数数组 nums。每一次操作中，你可以从 nums 中选择任意一个数，将其值减小为原来的一半。
请你返回将 nums 数组和至少减少一半的最少操作数。

说明：

  • 为了让操作次数最少，我们的贪心策略是：每次操作都必须选择当前数组中数值最大的那个元素进行减半。

  • 只有每次都最大程度地减少总和，才能以最少的次数达到总和减半的目标。

  • 示例：

    • 示例 1：
      1
      2
      3
      4
      5
      6
      7
      输入：nums = [5,19,8,1]
      输出：3
      解释：初始总和为 5+19+8+1 = 33，目标是减少到 16.5 以下。
      第1次：选19减半为9.5，数组变为 [5,9.5,8,1]，总和减少了9.5。
      第2次：选9.5减半为4.75，数组变为 [5,4.75,8,1]，总和减少了4.75。
      第3次：选8减半为4，数组变为 [5,4.75,4,1]，总和减少了4。
      此时总共减少了 9.5+4.75+4 = 18.25，超过了目标16.5，操作数为3。

💻 解题思路

思路1：贪心 + 最大堆（Python 取反模拟）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import heapq
from typing import List

class Solution:
    def halveArray(self, nums: List[int]) -> int:
        k = sum(nums)/2
        ans = 0
        cou = 0
        heapq.heapify_max(nums)
        while cou < k:
            val = heapq.heappop_max(nums)
            cou += val / 2
            heapq.heappush_max(nums,val/2)
            ans += 1
        return ans

📊 性能分析

  • 时间复杂度：O(nlog⁡n)O(n \log n)。建堆需要 O(n)O(n)，每次弹出和推入堆的操作需要 O(log⁡n)O(\log n)。
  • 空间复杂度：O(n)O(n)。主要为堆占用的空间。

💡 思考

这是一道典型的贪心算法结合优先队列(堆的题目。

  1. 贪心策略：每次选最大的数减半，能保证每次操作对总和的削减幅度最大。
  2. 数据结构选择：由于每次操作后，被减半的数会变小，需要重新与其他数比较大小以找出新的最大值，使用最大堆可以让我们在 O(1)的时间内获取最大值，并在 O(log⁡n)的时间内完成数据的更新。