[!info] related notes 算法面试题型 MOC 堆常见题

Halve Array Sum (Max-Heap)

LeetCode: https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/

思路

题目给定正整数数组，每次可把某个数减半，允许得到小数。同一个数可多次选择，不能只按原值排序后每个数减半一次。

• 用大根堆维护当前数值。
• 目标是让累计减少量 reduced >= sum / 2。

一次选择数值 x 可减少 x/2，随后该元素可贡献的减少量依次为 x/4、x/8……。每条序列递减，当前最大值对应所有可选下一步中最大的减少量；每次取最大能以最少操作达到目标。

Java Template

import java.util.*;

class Solution {
    public int halveArray(int[] nums) {
        PriorityQueue<Double> heap = new PriorityQueue<>(Collections.reverseOrder());
        double sum = 0;
        for (int v : nums) {
            sum += v;
            heap.add((double) v);
        }
        double target = sum / 2.0;
        double reduced = 0;
        int ops = 0;
        while (reduced < target) {
            double x = heap.poll();
            double half = x / 2.0;
            reduced += half;
            heap.add(half);
            ops++;
        }
        return ops;
    }
}

循环中取出旧值后把减半的新值放回堆。按本例逐个 add 的建堆方式，时间 O(n log n + t log n)，t 为操作数，空间 O(n)。正数条件下每个数减半一次是 n 次可行方案，贪心不会需要更多次数，因此整体 O(n log n)。

此处 double 适配题目范围内的正整数和反复除 2；不能把它当作任意精度实数或财务金额算法。

Related

• 堆常见题