fan4w
fan4w
发布于 2023-07-25 / 105 阅读 / 0 评论 / 0 点赞

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和数据结构的学习,任重道远啊


评论