---

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

• 标签：贪心、位运算、数组
• 难度：中等

题目链接

• 1558. 得到目标数组的最少函数调用次数 - 力扣

题目大意

描述：初始数组全为 $0$，可以执行两种操作：

1. 将任意一个元素加 $1$。
2. 将所有元素乘以 $2$。

给定目标数组 $nums$。

要求：返回将初始数组变为 $nums$ 所需的最少操作次数。

说明：

• $1 \le nums.length \le 10^5$。
• $0 \le nums[i] \le 10^9$。

示例：

• 示例 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 。

解题思路

思路 1：位运算 + 贪心

1. 核心思想

将所有数组元素视为二进制数。操作 $1$（加 $1$）负责将某些位从 $0$ 变 $1$。操作 $2$（乘以 $2$）负责左移操作。

考虑整体：

• 每个元素需要若干次加 $1$ 操作来设置二进制位。
• 所有元素共享乘 $2$ 操作（所有元素同时乘 $2$）。

对于每个 $nums[i]$，看其二进制表示：

• 执行加 $1$ 的次数 = 二进制中 $1$ 的个数（设置每个 $1$ 位需要一次加 $1$）。
• 执行乘 $2$ 的次数 = 二进制最高位的位置（每次乘 $2$ 对应左移一位）。

全局：

• 总加 $1$ 次数 = 所有元素二进制中 $1$ 的个数之和。
• 总乘 $2$ 次数 = 所有元素中最大二进制位长度减 $1$（因为初始全 $0$，乘 $2$ 从 $1$ 开始有效）。

2. 具体步骤

第 1 步：初始化 $add = 0$，$max\_bit = 0$。

第 2 步：遍历每个 $x$：

• $add += bit\_count(x)$（二进制中 $1$ 的个数）。
• $max\_bit = max(max\_bit, x.bit\_length() - 1)$（最高位位置）。

第 3 步：返回 $add + max(max\_bit, 0)$。如果所有元素为 $0$，$max\_bit = -1$，返回 $add$。

3. 举例说明

以 $nums = [1,5]$ 为例：

• $1$ 的二进制 1：$1$ 个 $1$，最高位 $0$。
• $5$ 的二进制 101：$2$ 个 $1$，最高位 $2$。

$add = 1 + 2 = 3$，$max\_bit = max(0, 2) = 2$。
总次数 $= 3 + 2 = 5$。

操作过程：

1. $+1$ → $[1,0]$（位置 $0$ 加 $1$）
2. $\times 2$ → $[2,0]$
3. $\times 2$ → $[4,0]$
4. $+1$ → $[4,1]$（位置 $1$ 加 $1$）
5. $+1$ → $[4,2]$
   不对，目标是 $[1,5]$...

等等，让我重新思考过程：
初始 $[0,0]$

1. 位置 $0$ 加 $1$ → $[1,0]$
2. 位置 $1$ 加 $1$ → $[1,1]$
3. 全部乘 $2$ → $[2,2]$
4. 位置 $1$ 加 $1$ → $[2,3]$
5. 全部乘 $2$ → $[4,6]$

不对，乘 $2$ 是所有同时。但这不对。

实际上，我们可以先全部加 $1$ 再乘 $2$：

1. 位置 $0$ 加 $1$ → $[1,0]$
2. 全部乘 $2$ → $[2,0]$
3. 位置 $1$ 加 $1$ → $[2,1]$
4. 全部乘 $2$ → $[4,2]$
5. 位置 $1$ 加 $1$ → $[4,3]$
   ...还是不对。

目标 $[1,5]$。$5$ 的二进制是 101，表示需要 $2^0$ 和 $2^2$。

换个思路：$0 \to [1,0] \to [1,1] \to [2,2] \to [2,4] \to [2,5] \to [1,5]$？

不对。让我给出一个可行的方案：

1. $+1$ pos1 → $[0,1]$
2. $\times 2$ → $[0,2]$
3. $\times 2$ → $[0,4]$
4. $+1$ pos1 → $[0,5]$
5. $+1$ pos0 → $[1,5]$

共 $5$ 步：$3$ 次加 $1$，$2$ 次乘 $2$。符合公式。

4. 关键理解

• 每次乘 $2$ 是所有元素一起乘 $2$。因此全局乘 $2$ 的次数由最大的那个数的二进制位数决定。
• 每个元素中的每个 $1$ 都需要一次加 $1$ 操作来设置。

思路 1：代码

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        add = 0
        max_bit = 0
        for x in nums:
            add += x.bit_count()
            max_bit = max(max_bit, x.bit_length() - 1)
        return add + max(max_bit, 0)

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。