【贪心】B049_LC_得到目标数组的最少函数调用次数（先将奇数变偶数，再将偶数除以二）

给你一个与 nums 大小相同且初始值全为 0 的数组 arr ，请你调用以上函数得到整数数组 nums 。

请你返回将 arr 变成 nums 的最少函数调用次数。

答案保证在 32 位有符号整数以内。

输入：nums = [1,5]
输出：5
解释：给第二个数加 1 ：[0, 0] 变成 [0, 1] （1 次操作）。
将所有数字乘以 2 ：[0, 1] -> [0, 2] -> [0, 4] （2 次操作）。
给两个数字都加 1 ：[0, 4] -> [1, 4] -> [1, 5] （2 次操作）。
总操作次数为：1 + 2 + 2 = 5 

提示：
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9

方法一：贪心

我的做法是先将奇数变偶数，然后将偶数除以二，可以更快地减少到 0，正确性有待证明

class Solution {
public:
    int minOperations(vector<int>& A) {
        int n=A.size(), ans=0; sort(A.begin(), A.end());
        while (A.back()) {
            for (int i=0; i<n; i++) if (A[i]&1) {
                A[i]--, ans++;
            }
            for (int i=0; i<n; i++) {
                A[i]/=2;
            }
            ans++;                        
        }
        return ans-1;
    }
};

复杂度分析

• Time：$O(nlogn)$，
• Space：$O(1)$

最后

以上就是可靠小天鹅为你收集整理的【贪心】B049_LC_得到目标数组的最少函数调用次数（先将奇数变偶数，再将偶数除以二）的全部内容，希望文章能够帮你解决【贪心】B049_LC_得到目标数组的最少函数调用次数（先将奇数变偶数，再将偶数除以二）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。