本文出自:Bert's Blog

题目简介

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

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

示例一:
输入：nums = [5,19,8,1]
输出：3
解释：初始 nums 的和为 5 + 19 + 8 + 1 = 33 。
以下是将数组和减少至少一半的一种方法：
选择数字 19 并减小为 9.5 。
选择数字 9.5 并减小为 4.75 。
选择数字 8 并减小为 4 。
最终数组为 [5, 4.75, 4, 1] ，和为 5 + 4.75 + 4 + 1 = 14.75 。
nums 的和减小了 33 - 14.75 = 18.25 ，减小的部分超过了初始数组和的一半，18.25 >= 33/2 = 16.5 。
我们需要 3 个操作实现题目要求，所以返回 3 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。

示例二:
输入：nums = [3,8,20]
输出：3
解释：初始 nums 的和为 3 + 8 + 20 = 31 。
以下是将数组和减少至少一半的一种方法：
选择数字 20 并减小为 10 。
选择数字 10 并减小为 5 。
选择数字 3 并减小为 1.5 。
最终数组为 [1.5, 8, 5] ，和为 1.5 + 8 + 5 = 14.5 。
nums 的和减小了 31 - 14.5 = 16.5 ，减小的部分超过了初始数组和的一半， 16.5 >= 31/2 = 16.5 。
我们需要 3 个操作实现题目要求，所以返回 3 。
可以证明，无法通过少于 3 个操作使数组和减少至少一半。

提示：
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;
    }
};

原文链接:https://ixfish.cn/index.php/archives/3/