2023年7月25日每日一题--2208. 将数组和减半的最少操作次数

leetcode链接：
2208. 将数组和减半的最少操作次数

题目分析

方案一

优先队列

class Solution {
    public int halveArray(int[] nums) {
        int result = 0;
        PriorityQueue<Double> queue = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1)); // 想让谁大，谁在外面
        long sum = 0;
        for (int num : nums) {
            sum += num;
            queue.add((double) num);
        }

        double mid = sum / 2.0;
        double sumMid = 0.0;
        while (sumMid < mid) {
            double v = queue.poll() / 2;
            sumMid += v;
            queue.add(v);
            result++;
        }
        
        return result;
    }
}

结果

解答成功:
执行耗时:183 ms,击败了36.36% 的Java用户
内存消耗:55.8 MB,击败了65.15% 的Java用户

分析

时间复杂度：
O( )

空间复杂度：
O( n )

官方题解

https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/solution/jiang-shu-zu-he-jian-ban-de-zui-shao-cao-4lej/

class Solution {
    public int halveArray(int[] nums) {
        PriorityQueue<Double> pq = new PriorityQueue<Double>((a, b) -> b.compareTo(a));
        for (int num : nums) {
            pq.offer((double) num);
        }
        int res = 0;
        double sum = 0;
        for (int num : nums) {
            sum += num;
        }
        double sum2 = 0.0;
        while (sum2 < sum / 2) {
            double x = pq.poll();
            sum2 += x / 2;
            pq.offer(x / 2);
            res++;
        }
        return res;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/solution/jiang-shu-zu-he-jian-ban-de-zui-shao-cao-4lej/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。