得到目标数组的最少函数调用次数 图解题解
这道题到底在问什么
- 输入
- nums=[1,5]
- 输出
- 5
- 输入
- nums=[2,2]
- 输出
- 3
- 输入
- nums=[4,2,5]
- 输出
- 6
最优解：一步一步想明白
- 3记牢:答案 = 所有数二进制里 1 的总个数(每个 1 要一次 +1)+ 最大数最高位的层数(每升一层一次共享的 ×2)。两块相加就是最少操作次数。
- 4先看清画面。上面这排格子是目标 nums = [4,2,5]。你手里的 arr 现在是 [0,0,0],要靠不停地 +1 和 ×2 把它拼成 nums。右边面板会一边拆二进制一边记两件事:用了多少次 +1,以及最高位爬到了第几层。我们先把每个数写成二进制来分析。
- 5思路拆成两件事。第一件,把三个数全写成二进制,数一数总共有多少个 1,每个 1 都要花一次 +1。第二件,找出最大的数最高位落在第几层,从第 0 层往上每升一层要做一次全体 ×2,而这一步是所有数共享的。下面一个数一个数地拆。
- 6看第 0 个数 4。把它写成 3 位二进制是 100,右边表格记下这一行。接着从高位到低位扫一遍,凡是 1 的位都要记一次 +1,顺便留意它最高的那个 1 在第几层。
- 74 的第 2 位是 1,说明拼这个数时,这一层上有一个 1 要靠一次 +1 放上去,+1 的累计变成 1。第 2 层是目前最高的有 1 的层,把最高层记成 2。
- 84 的第 1 位、第 0 位都是 0,这些位上没有 1 要放,直接跳过,不增加 +1 的次数。4 这个数就拆完了,它一共贡献了 1 个 1。
- 9看第 1 个数 2。把它写成 3 位二进制是 010,右边表格记下这一行。接着从高位到低位扫一遍,凡是 1 的位都要记一次 +1,顺便留意它最高的那个 1 在第几层。
- 102 的第 1 位是 1,说明拼这个数时,这一层上有一个 1 要靠一次 +1 放上去,+1 的累计变成 2。第 1 层没有超过已有最高层 2,最高层仍记 2。
- 112 的第 2 位、第 0 位都是 0,这些位上没有 1 要放,直接跳过,不增加 +1 的次数。2 这个数就拆完了,它一共贡献了 1 个 1。
- 12看第 2 个数 5。把它写成 3 位二进制是 101,右边表格记下这一行。接着从高位到低位扫一遍,凡是 1 的位都要记一次 +1,顺便留意它最高的那个 1 在第几层。
- 135 的第 2 位是 1,说明拼这个数时,这一层上有一个 1 要靠一次 +1 放上去,+1 的累计变成 3。第 2 层跟当前最高层持平,最高层仍是 2。
- 145 的第 0 位是 1,说明拼这个数时,这一层上有一个 1 要靠一次 +1 放上去,+1 的累计变成 4。第 0 层没有超过已有最高层 2,最高层仍记 2。
- 155 的第 1 位都是 0,这些位上没有 1 要放,直接跳过,不增加 +1 的次数。5 这个数就拆完了,它一共贡献了 2 个 1。
- 16三个数都拆完了。4 有 1 个 1,2 有 1 个 1,5 有 2 个 1,加起来一共 4 个 1。每个 1 都要一次 +1,所以单独的 +1 操作总共要做 4 次。这是答案的第一块。
- 17再看最高位。4 和 5 的最高位都落在第 2 层,这是所有数里最高的。要把某一层的 1 抬到第 2 层,得从第 0 层开始一层层往上乘,正好 2 次全体 ×2。这是答案的第二块。
- 18为什么 ×2 不用每个数各算一遍?因为一次 ×2 会把数组里所有数同时左移一位,是大家共享的一步,次数是全局只数一遍的。位数较低的数需要的 1,会在对应的那一层直接用一次 +1 补上,它并没有提前乘好、再一路跟着被抬高,所以不会被后面的 ×2 多抬。这样 ×2 的次数只由最高的那个数决定,取最高层就够了。
- 19两块加起来。4 次单独的 +1,加上 2 次共享的 ×2,最少操作次数就是 6。整道题没有真去一步步构造,只把每个数拆成二进制、数 1 加最高层就出答案。下面我们倒着减一遍来验算这个 6。
- 20换个方向验证。正着是从全 0 拼出 nums,倒着就是从 nums 一步步减到全 0。+1 的逆操作是给奇数减 1,×2 的逆操作是全体减半。我们反着走一遍,数一数减 1 用了几次、减半用了几次,应该和刚才的 4 加 2 完全对上。
- 21当前数组是 [4,2,5]。先找奇数,因为奇数的个位是 1,这个 1 没法靠减半消掉,只能减 1。这一轮第 2 位是奇数,标红,准备逐个减 1。
- 22给第 2 位减 1,数组变成 [4,2,4],减 1 的次数累计到 1。每一次减 1,对应正向时的一次 +1。
- 23现在数组里全是偶数且还没归零,可以整体减半,变成 [2,1,2],减半次数累计到 1。每一次减半,对应正向时的一次全体 ×2,是所有数共享的一步。
- 24当前数组是 [2,1,2]。先找奇数,因为奇数的个位是 1,这个 1 没法靠减半消掉,只能减 1。这一轮第 1 位是奇数,标红,准备逐个减 1。
- 25给第 1 位减 1,数组变成 [2,0,2],减 1 的次数累计到 2。每一次减 1,对应正向时的一次 +1。
- 26现在数组里全是偶数且还没归零,可以整体减半,变成 [1,0,1],减半次数累计到 2。每一次减半,对应正向时的一次全体 ×2,是所有数共享的一步。
- 27当前数组是 [1,0,1]。先找奇数,因为奇数的个位是 1,这个 1 没法靠减半消掉,只能减 1。这一轮第 0 位、第 2 位是奇数,标红,准备逐个减 1。
- 28给第 0 位减 1,数组变成 [0,0,1],减 1 的次数累计到 3。每一次减 1,对应正向时的一次 +1。
- 29给第 2 位减 1,数组变成 [0,0,0],减 1 的次数累计到 4。每一次减 1,对应正向时的一次 +1。
- 30数组减到全 0,收工。数一数:减 1 一共做了 4 次,正好等于所有数二进制里 1 的个数;减半一共做了 2 次,正好等于最高位的层数。4 加 2 等于 6,和二进制法算出的 6 一模一样,验算通过。
⚠️ 容易写错的地方
✗ 错：把 ×2 按每个数分别累加:每个数各算一遍升位次数
✓ 对：×2 是全体共享的,只按最大数最高位那一层算
一次 ×2 同时把所有数左移一位,次数是全局共享的。位数较低的数需要的 1,是在对应层数再用 +1 放进去的,不会被后续 ×2 多抬,所以不必为它单独累加升位。若给每个数单独累加升位次数,会严重重复计数,把答案算大。正确做法是 +1 各自承担、×2 的次数就按最高位那一层算
✗ 错：数组全是 0 时,最高位层数算成负数
✓ 对：用 max(0, bit_length 减 1) 或借 "0" 的字符串长度挡住
arr 本来就是全 0,若 nums 也全是 0,一次操作都不用、答案是 0。但 0 的 bit_length 是 0,直接减 1 会得到 负 1。Python 用 max(0, ...) 兜底,Java 用 toBinaryString 得到 "0" 长度 1 减 1 恰好为 0,C++ 用 if(mx) 守住,三者都在防这个 0 的边界
✗ 错：只数最高位的 1,漏掉一个数里其它位的 1
✓ 对：一个数所有为 1 的位都要各记一次 +1
+1 的总数等于所有数二进制里 1 的总个数,而不是数的个数,也不是只看最高位。比如 5 是 101,有两个 1,要算两次 +1。用 popcount 类函数一次性数清一个数里全部的 1 才不会漏
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def minOperations(self, nums: List[int]) -> int:
return sum(v.bit_count() for v in nums) + max(0, max(nums).bit_length() - 1)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int minOperations(vector<int>& nums) {
int ans = 0;
int mx = 0;
for (int v : nums) {
mx = max(mx, v);
ans += __builtin_popcount(v);
}
if (mx) ans += 31 - __builtin_clz(mx);
return ans;
}
};Java
import java.util.*;
class Solution {
public int minOperations(int[] nums) {
int ans = 0;
int mx = 0;
for (int v : nums) {
mx = Math.max(mx, v);
ans += Integer.bitCount(v);
}
ans += Integer.toBinaryString(mx).length() - 1;
return ans;
}
}复杂度
时间
O(n)
n 是数组长度。只从头到尾扫一遍,每个数做的是一次求 1 的个数、一次取最大值,都是字宽内的常数操作,所以总体是线性的 O(n)。本题 n 最大到 10 的 5 次方,线性扫描轻松通过。若按位宽更严格地算,是 O(n 乘以 log 最大值),但每个数不超过 10 的 9 次方、位宽固定在 30 位上下,实际就是常数,所以记 O(n) 即可
空间
O(1)
按峰值算。整个过程只用了答案计数器 ans 和记录最大值的 mx 两个变量,不随 n 增长,也不开任何额外数组,所以额外空间是常数 O(1)。三种语言都只是一遍遍历加几个标量变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 得到目标数组的最少函数调用次数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么答案能拆成「1 的个数」加「最高位层数」这两块,不会互相影响?+
因为两种操作各司其职。+1 负责在某一层放上一个 1,放几个 1 就要几次 +1,这完全由各个数二进制里 1 的总数决定。×2 负责把整体抬高一层,它不改变任何数里 1 的个数,只决定这些 1 最终落在第几层。一个管「放多少个 1」,一个管「抬多高」,互不干扰,所以可以分别数清再相加。
不去真的构造 arr,怎么保证这个次数真的是最少的?+
从必要性看,每个为 1 的位至少要一次 +1 才能出现,最高位要到第 k 层至少要 k 次 ×2 才能抬上去,所以答案不会比这个公式更小。从可行性看,我们确实能用这么多次拼出来:在合适的层上做 +1、需要升层时做 ×2,逆向减半的模拟也演示了这套操作真的能把 nums 减到全 0。下界和上界对上了,所以它就是最少次数。
题目说每个数能到 10 的 9 次方,会不会有溢出风险?+
基本不会。我们从头到尾没有真的去乘 2 构造大数,只是对原始的每个数做求 1 的个数和取最大值,这些都在数本身的范围里。10 的 9 次方在 32 位整数范围内,popcount 类函数处理它没有问题。最后的答案题目也保证落在 32 位有符号整数以内,所以用普通的 int 累加就够了。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 得到目标数组的最少函数调用次数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。