将数组和减半的最少操作次数【LC2208】
给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）
请你返回将 nums 数组和 至少 减少一半的 最少 操作数。
- 思路：贪心+大顶堆
- 要使操作数最少，每次操作减小的值应尽可能大。【贪心】
- 使用大顶堆存储数组中最大的元素，每次对堆顶元素减小一半，并将减小后的元素放入堆中，反复操作，直至减小的总和大于和的一半
- 实现
class Solution { public int halveArray(int[] nums) { PriorityQueue<Double> pq = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1)); double sum = 0.0; for (int num : nums){ sum += num; pq.add(num + 0.0); } sum /= 2; int count = 0; while (sum > 0){ double num = pq.poll(); sum -= num / 2; pq.add(num / 2); count++; } return count; } }
复杂度
- 时间复杂度：O(nlogn)
- 空间复杂度：O ( n )
