【LeetCode 算法】Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数-Greedy-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode 算法】Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数-Greedy。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

问题描述：

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

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

$1 <= nums.length <= 10^5\\ 1 <= nums[i] <= 10^7$

分析

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

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

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

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

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

而且为了使得能够尽快使 $s^{'}$ 靠近到目标 $ha l f$ ，每次一定是选择当前数组中的 $ma x$ ，进行操作。

暴力

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

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

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

优先队列

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

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

代码

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;
    }