解决这个问题的关键是：每次必须选择当前最大的元素减半。
如果要高效地 “每次获取最大元素”，大根堆无疑是最佳选择。
方法 1：用 PriorityQueue 实现
使用 Java 内置的PriorityQueue作为大根堆，直接存储double类型的元素。
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
|
public static int halveArray(int[] nums) {
// 大根堆：通过比较器(b.compareTo(a))实现，确保堆顶是最大元素
PriorityQueue<Double> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));
double sum = 0;
// 计算数组总和，并将所有元素加入大根堆
for (int num : nums) {
heap.add((double) num);
sum += num;
}
// 减少的总量至少为原总和的一半
sum /= 2;
int ans = 0;
double minus = 0; // 累计减少的总量
// 每次取最大元素减半，直到累计减少量≥目标
while (minus < sum) {
ans++; // 操作次数+1
double cur = heap.poll() / 2; // 取出最大元素，减半
minus += cur;
heap.add(cur); // 减半后的元素放回堆中
}
return ans;
}
|
方法 2：自定义大根堆（用整数避免浮点数精度问题）
使用自定义的大根堆，并且用long类型存储元素（通过左移 20 位放大元素），避开浮点数精度陷阱。
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
public int halveArray(int[] nums) {
int n = nums.length;
long[] heap = new long[n];
long sum = 0;
for (int i = n - 1; i >= 0; i--) {
// 放大2^20倍（足够覆盖1e9的精度，避免浮点数）
heap[i] = (long) nums[i] << 20;
sum += heap[i];
heapify(heap, n, i);
}
sum /= 2;
int ans = 0;
long minus = 0;
while (minus < sum) {
ans++;
// 堆顶减半（整数操作，无精度问题）
heap[0] >>= 1; // 右移1位 = 除以2，比/=2更快
minus += heap[0];
// 调整堆顶
heapify(heap, n, 0);
}
return ans;
}
private void heapify(long[] heap, int size, int i) {
// 暂存当前节点值，避免重复访问heap[i]
long curVal = heap[i];
// 左孩子索引
int left = i * 2 + 1;
while (left < size) {
// 暂存左孩子值，减少数组访问
long leftVal = heap[left];
// 右孩子值：存在则取，不存在则设为极小值（不影响比较）
long rightVal = (left + 1 < size) ? heap[left + 1] : Long.MIN_VALUE;
//选左右孩子中更大的那个
int largerChild = (rightVal > leftVal) ? left + 1 : left;
long largerVal = (largerChild == left) ? leftVal : rightVal;
//若当前节点值 >= 较大孩子值，堆结构已满足，退出
if (curVal >= largerVal) {
break;
}
//直接将较大孩子值覆盖到当前节点
heap[i] = largerVal;
// 更新当前节点索引，继续向下调整
i = largerChild;
left = i * 2 + 1;
}
//将暂存的当前节点值放到最终位置
heap[i] = curVal;
}
|
完整代码
链接：https://pan.quark.cn/s/2ed207e367ac
提取码：3H47