得到目标数组的最少函数调用次数

难度: Medium

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

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

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

示例 1：

输入：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 。

示例 2：

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

示例 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 数组）。

示例 4：

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

示例 5：

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

提示：

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

Submission

运行时间: 36 ms

内存: 23.5 MB

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        op1 = sum(v.bit_count() for v in nums)
        op2 = max(0,max(nums).bit_length()-1)
        return op1 + op2

Explain

此题解通过反向思维来求解：考虑如何从数组 `nums` 逆向得到全零数组。首先，计算每个数字需要多少次加法操作，即每个数字的二进制表示中 '1' 的个数，这些 '1' 都需要一次加法操作来实现。其次，考虑数组中的最大值，需要乘2的操作次数是最大数的二进制位长度减1（因为从1开始，乘2达到相应长度）。因此，总的操作次数为所有数字需要的加法次数之和加上最大数需要的乘法次数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        # 计算所有数字中二进制表示的1的总数
        op1 = sum(v.bit_count() for v in nums)
        # 计算最大数字的二进制长度 - 1，即乘2的最大次数
        op2 = max(0, max(nums).bit_length() - 1)
        # 返回加法和乘法需要的总次数
        return op1 + op2

Explore

从1开始乘2到达当前数字需要的次数是该数字二进制长度减1。比如，数字8的二进制为'1000'，长度为4，但从1开始，只需要连续乘2三次（1, 2, 4, 8）就可以达到8，故需要减1。

每个二进制位的1代表了在那个位置上的加法操作。例如，二进制数'101'代表了在2^0和2^2位置上分别加1，总共两次加法。因此，计算所有数字的二进制中1的总数可以准确得到进行这些加法操作的总次数。

这是为了处理数组`nums`中含有0的情况。因为0的二进制长度是0，计算`0 - 1`会得到-1，这在逻辑上不成立（因为我们不会做任何乘2操作）。使用`max(0, ...)`是为了确保操作次数不会小于0。

对于包含零的情况，算法仍有效，因为0的加法操作次数是0，乘法操作次数也被`max(0, ...)`处理。如果包含负数，算法将不适用，因为负数的二进制表示（补码）和算法的逻辑不符，需要额外处理或修改算法逻辑以适应负数。