LeetCode每日一题：2208. 将数组和减半的最少操作次数

题目链接：2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）

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

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

看到本题想到的方法是贪心算法，每次都把数组中最大的值减半，这样操作次数一定是最少的，先贴我写的代码：

class Solution {
public:
    int halveArray(vector<int>& nums) {
        double sum=0;
        int ans=0;
        int n=nums.size();
        vector<double> dnums;
        double max=0;
        int pmax;
        for(int i=0;i<n;i++){
            sum+=nums[i];
            dnums.push_back(nums[i]);
            if(nums[i]>max){
                max=nums[i];
                pmax=i;
            }
        }
        double diff=sum/2.0;
        while(diff>0){
            max/=2.0;
            diff-=max;
            ans++;
            dnums[pmax]/=2.0;
            for(int i=0;i<n;i++){
                if(dnums[i]>max){
                    max=dnums[i];
                    pmax=i;
                }
            }
        }
        return ans;
    }
};

最后结果是超时了，因为每次寻找最大值时都遍历了一遍数组，时间复杂度为O(n)

而根据官方题解改进的结果如下：

class Solution {
public:
    int halveArray(vector<int>& nums) {
        std::priority_queue<double> pq(nums.begin(),nums.end());
        int ans=0;
        double sum = accumulate(nums.begin(),nums.end(),0.0);
        double diff=sum/2;
        while(diff>0){
            double n = pq.top();
            pq.pop();
            diff-=n/2;
            pq.push(n/2);
            ans++;
        }
        return ans;
    }
};

可以看到，官方题解主要改进之处在于使用了一个PriorityQueue，std::priority_queue通过维护一个大顶堆，实现了更高效的寻找最大值，有效降低了时间复杂度

看来STL和数据结构的学习，任重道远啊