Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数

问题描述：

给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）

请你返回将 nums 数组和 至少 减少一半的 最少 操作数。

$$\begin{gathered} 1<=nums.length<=10^5 \\ 1<=nums[i]<=10^7 \end{gathered}$$

分析

目标是将数组的和减少到原始数组和的一半，而且是最小的操作数。

一次操作可以选任意的元素减半，而且可以重复选择某个下标的元素。所以几乎不存在限制。

也就是说一定在经过若干次操作后，可以达到目标。

记原始数组和为$sum$，那么目标就是$half=sum/2$;
但是问题是要求最少的，所以细化一下目标，

• 如果最后一次的操作使得最新的数组和$s^{\prime }==half$，说明这是最后一次操作，
• 同样如果$s^{\prime }<half$,也是说明最后一次操作。
• 如果$s^{\prime }>half$,说明还需要进行操作。

而且为了使得能够尽快使$s^{\prime }$靠近到目标$half$，每次一定是选择当前数组中的$max$，进行操作。

暴力

如果是暴力的算法，就是每次选择最大，然后减半，放回去，再找一次最大，循环往复。

每次找数组的最大值的时间复杂度$O(N)$,而且要达到目标需要操作N次，整体的时间复杂度为$O(N^2)$.

所以这个暴力的时间复杂度有TLE的风险。

优先队列

所以就需要进行加速，而唯一能选的就是优先队列。
在优先队列中的维护一个最大值或最小值的平均时间复杂度是$O(logN)$,所以整体的时间复杂度就会降低到$O(NlogN)$.

同时需要注意的是数据的范围，以及精度。

代码

TLE

public int halveArray(int[] nums) {Double tot = 0.0;int n = nums.length;Double[] arr = new Double[n];for(int i =0;i<n;i++){arr[i] = nums[i]*1.0;tot+= arr[i];}Double half = tot*0.5;int ans =0;for(int i =0;i<n;i++){if(half<=0) break;int id =0;double max = arr[id];for(int j =0;j<n;j++){if(arr[j]>max){max = arr[j];id = j;}}arr[id] *= 0.5;half -= arr[id];ans++;}return ans;}

时间复杂度$O(N^2)$

空间复杂度$O(1)$

优先队列

public int halveArray(int[] nums) {PriorityQueue<Double> pq = new PriorityQueue<Double>((a,b)->{return b.compareTo(a);});Double tot = 0.0;for(int num: nums){Double t = num*1.0;tot+=t;pq.offer(t);}          Double half = tot*0.5;int ans =0;while(half>0&&!pq.isEmpty()){Double t = pq.poll();t *=0.5;half -= t;ans++;pq.offer(t);}return ans;}

时间复杂度$O(NlogN)$

空间复杂度$O(N)$

Tag

Array

Greedy

Heap