题目描述
给你一个正整数数组 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 。
可以证明，无法通过少于 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 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 107
解法
方法一：贪心 + 优先队列（大根堆）
根据题目描述，每一次操作，都会将数组中的一个数减半。要使得数组和至少减少一半的操作次数最少，那么每一次操作都应该选择当前数组中的最大值进行减半。
因此，我们先算出数组要减少的总和 $s$，然后用一个优先队列（大根堆）维护数组中的所有数，每次从优先队列中取出最大值 $t$，将其减半，然后将减半后的数重新放入优先队列中，同时更新 $s$，直到 $s \le 0$ 为止。那么此时的操作次数就是答案。
时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def halveArray(self, nums: List[int]) -> int:
s = sum(nums) / 2
h = []
for v in nums:
heappush(h, -v)
ans = 0
while s > 0:
t = -heappop(h) / 2
s -= t
heappush(h, -t)
ans += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public int halveArray(int[] nums) {
double s = 0;
PriorityQueue<Double> q = new PriorityQueue<>(Collections.reverseOrder());
for (int v : nums) {
q.offer(v * 1.0);
s += v;
}
s /= 2.0;
int ans = 0;
while (s > 0) {
double t = q.poll();
s -= t / 2.0;
q.offer(t / 2.0);
++ans;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
public:
int halveArray(vector<int>& nums) {
priority_queue<double> q;
double s = 0;
for (int& v : nums) {
s += v;
q.push(v);
}
s /= 2.0;
int ans = 0;
while (s > 0) {
double t = q.top() / 2;
q.pop();
s -= t;
q.push(t);
++ans;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | func halveArray(nums []int) (ans int) {
var s float64
q := hp{}
for _, x := range nums {
s += float64(x)
heap.Push(&q, float64(x))
}
s /= 2
for s > 0 {
x := heap.Pop(&q).(float64)
ans++
s -= x / 2
heap.Push(&q, x/2)
}
return
}
type hp struct{ sort.Float64Slice }
func (h hp) Less(i, j int) bool { return h.Float64Slice[i] > h.Float64Slice[j] }
func (h *hp) Push(v any) { h.Float64Slice = append(h.Float64Slice, v.(float64)) }
func (h *hp) Pop() any {
a := h.Float64Slice
v := a[len(a)-1]
h.Float64Slice = a[:len(a)-1]
return v
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | function halveArray(nums: number[]): number {
let s: number = nums.reduce((a, b) => a + b) / 2;
const h = new MaxPriorityQueue();
for (const v of nums) {
h.enqueue(v, v);
}
let ans: number = 0;
while (s > 0) {
let { element: t } = h.dequeue();
t /= 2;
s -= t;
h.enqueue(t, t);
ans += 1;
}
return ans;
}
|
方法二