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

题目简介

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

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

提示:
1 <= nums.length <= 105
1 <= nums[i] <= 107


代码模板

class Solution {
public:
    int halveArray(vector<int>& nums) {
        
    }
};

简单分析

要求数组减半的次数,只需要求在数组恰好减半时,程序执行了多少次,并返回结果。如果要求的是最少次数的话,那就需要程序在执行每次操作的时候,尽可能减少比较大的数。要满足这个要求,我们可以在每次操作的时候减少数组中最大的数。

那要实现这个功能,我们可以这样操作:将输入的数据进行求和,并用两个变量来分别存储程序执行的次数以及【多次操作执行后减少的数据和】,将减少的数据和与原来的数据和进行比较,如果减少的数据和大于 或等于 原数据和的一半,那就应该停止对数据进行减半求和,并返回操作执行次数。

class Solution {
public:
    int halveArray(vector<int>& nums) {
        int m = nums.size();
        double n,j,d,k,q;
      
        //获取nums之和
        k = 0,j=0,n=0;
        k = accumulate(_nums.begin(), _nums.end(), 0.0);

        q = k / 2.0;
        for (int cptime=0;j<q;cptime++)
        {
            d = 0;
            //求最大值
            int max_number = 0;
            for (int ncptime = 1; ncptime <= m; ncptime++)
            {
                if (_nums[ncptime - 1] >= max_number)
                {
                    max_number = _nums[ncptime - 1];
                    d = ncptime - 1;
                }
                else
                {
                    continue;
                }
            }
            //减半,重新计数
            _nums[d] = _nums[d]/2.0;
            j += _nums[d];
            n = cptime+1;
        }
        return n;
    }
};

但这段代码是存在问题的,因为原数据是以 vector<int> 的数据类型进行存储的。所以当对其中的奇数如19进行减半后,结果9.5并不能存入数组内,而是会转化为整数后进行存储,这样会导致最后出现错误的结果。
因此,我们需要将原数组的数据类型进行转化后,再进行操作。修正后的代码如下:

class Solution {
public:
    int halveArray(vector<int>& nums) {
        int m = nums.size();
        double n,j,d,k,q;

        //转换数组
        vector<double> _nums;
        for (int i = 0; i < m; i++) {
            double converted = static_cast<double>(nums[i]);
            _nums.push_back(converted);
        }
        //获取nums之和
        k = 0,j=0,n=0;
        k = accumulate(_nums.begin(), _nums.end(), 0.0);

        q = k / 2.0;
        for (int cptime=0;j<q;cptime++)
        {
            d = 0;
            //求最大值
            int max_number = 0;
            for (int ncptime = 1; ncptime <= m; ncptime++)
            {
                if (_nums[ncptime - 1] >= max_number)
                {
                    max_number = _nums[ncptime - 1];
                    d = ncptime - 1;
                }
                else
                {
                    continue;
                }
            }
            //减半,重新计数
            _nums[d] = _nums[d]/2.0;
            j += _nums[d];
            n = cptime+1;
        }
        return n;
    }
};

使用STL库(优先队列)降低算法的时间复杂度

上方的代码虽然可以解决大部分问题,但算法的时间复杂度为$n^2$,如果处理大样本数据,效率可能会非常低下。实际上,上方代码也是无法完美通过leetcode的所有样本的(即大数据样本)。因此我们可以考虑改进算法以将其时间复杂度降低到$logn$。当然,我们可以在原代码上修改,但其实还有一个比较好的方法是使用优先队列。
在对最大值进行处理时,优先队列是一种比较适合的数据结构,优先队列是队列的一种,而队列也是c++中的一种STL库。合理使用STL库不仅可以减少代码量,而且还可以降低算法的时间复杂度,提高程序的运行效率。(当然,如果你认为效率还是不够,也可以自己设计一种更好的算法)
按照原来的思路改写代码,我们可以得到最终版本的代码:

class Solution {
public:
    int halveArray(vector<int>& nums) {
        double m,n,j;
        j = 0.0;
        int q;
        q = 0;
        //转换数组
        vector<double> _nums(nums.begin(), nums.end());
        //计算数组之和
        m = accumulate(_nums.begin(), _nums.end(), 0.0);
        n = m / 2;
        //创建优先队列
        priority_queue<double> k(_nums.begin(), _nums.end());
        //减半运算求值
        while (j < n && !k.empty())
        {
            double maxnumber = -1;
            maxnumber = k.top();
            k.pop();
            maxnumber /= 2.0;
            k.push(maxnumber);
            j += maxnumber;
            q++;
        }
        return q;
    }
};

打赏
文章目录