题目描述

func modify(arr, op, idx) {
    // add by 1 index idx
    if (op == 0) {
        arr[idx] = arr[idx] + 1
    }
    // multiply by 2 all elements
    if (op == 1) {
        for (i = 0; i < arr.length; i++) {
            arr[i] = arr[i] * 2
        }
    }
}

请你调用以上函数，从一个与 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。

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

输入：nums = [4,2,5]
输出：6
解释：（初始）[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] ->
              [2,1,2] -> [4,2,4] -> [4,2,5]（nums 数组）。

输入：nums = [3,2,2,4]
输出：7

输入：nums = [2,4,8,16]
输出：8

限制

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

算法

(贪心) $O(n \log S)$

1. 先来看一个数字的情况。初始是 0，目标是 x，通过加 1 或者乘 2 的操作变到 x 的最少次数可以如下计算
   • 如果 x 为偶数，则除以 2，次数加一。如果中途出现了奇数，则减 1，次数加一。
2. 整个数组的每个数字可以都按照这个方法来计算，我们找到需要最多乘 2 操作的数字，假设次数为 m，整个数组就只需要进行 m 次整体乘 2 的操作。然后再加上每个数字需要的加 1 操作就可以了。

时间复杂度

• 每个数字需要 $O(\log S)$ 的时间计算，故总时间复杂度为 $O(n \log S)$，其中 $S$ 为最大的数字。

空间复杂度

• 仅需要常数的额外空间。

Go 代码

func minOperations(nums []int) int {
    tot := 0
    maxCounter := 0
    for _, v := range nums {
        counter := 0
        for v > 1 {
            if v%2 == 1 {
                v--
                tot++
            }
            v /= 2
            counter++
        }

        if v == 1 {
            tot++
        }

        if maxCounter < counter {
            maxCounter = counter
        }
    }

    return tot + maxCounter
}