2208. 将数组和减半的最少操作次数

你能为这个世界做的最好的事，就是充分发挥自己的才能。

LC每日一题，参考2208. 将数组和减半的最少操作次数，难度1550分。

题目

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

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

输入：nums = [5,19,8,1]   
输出：3

解题思路

• 优先队列：使用优先队列，每次减少最大元素的一半，所以需要大根堆。

优先队列

class Solution {
    public int halveArray(int[] nums) {
        //每次优先减少数值大的数
        int ans = 0;
        double sum = 0;
        for(int i : nums) sum += i;
        //优先队列 大根堆
        PriorityQueue<Double> pq = new PriorityQueue<>((a,b)->a>b?-1:1);//比较返回整数
        for(int i : nums) pq.add((double)i);
        double tmp = 0;
        sum /= 2;
        while(tmp < sum) {
            double top = pq.poll();
            tmp += top/2;
            pq.add(top/2);
            ans ++;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(nlogn)，n为数组长度，优先队列中元素n个，每次添加logn。
• 空间复杂度：O(n)。