题目

标题和出处

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

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

难度

6 级

题目描述

要求

给定一个正数数组nums \texttt{nums}nums。有一个相同长度且初始值全为0 \texttt{0}0的数组arr \texttt{arr}arr。还有modify \texttt{modify}modify函数：

现需要尽可能少地调用该函数将arr \texttt{arr}arr变成nums \texttt{nums}nums。

返回将arr \texttt{arr}arr变成nums \texttt{nums}nums的最少函数调用次数。

答案保证在32 \texttt{32}32位有符号整数范围内。

示例

示例 1：

输入：nums = [1,5] \texttt{nums = [1,5]}nums = [1,5]
输出：5 \texttt{5}5
解释：给第二个数加1 \texttt{1}1：[0, 0] → [0, 1] \texttt{[0, 0]} \rightarrow \texttt{[0, 1]}[0, 0]→[0, 1]（1 \texttt{1}1次操作）。
将所有数字乘以2 \texttt{2}2：[0, 1] → [0, 2] → [0, 4] \texttt{[0, 1]} \rightarrow \texttt{[0, 2]} \rightarrow \texttt{[0, 4]}[0, 1]→[0, 2]→[0, 4]（2 \texttt{2}2次操作）。
给两个数字都加1 \texttt{1}1：[0, 4] → [1, 4] → [1, 5] \texttt{[0, 4]} \rightarrow \texttt{[1, 4]} \rightarrow \texttt{[1, 5]}[0, 4]→[1, 4]→[1, 5]（2 \texttt{2}2次操作）。
总操作次数为：1 + 2 + 2 = 5 \texttt{1} + \texttt{2} + \texttt{2} = \texttt{5}1+2+2=5。

示例 2：

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

示例 3：

输入：nums = [4,2,5] \texttt{nums = [4,2,5]}nums = [4,2,5]
输出：6 \texttt{6}6
解释：[0,0,0] → [1,0,0] → [1,0,1] → [2,0,2] → [2,1,2] → [4,2,4] → [4,2,5] \texttt{[0,0,0]} \rightarrow \texttt{[1,0,0]} \rightarrow \texttt{[1,0,1]} \rightarrow \texttt{[2,0,2]} \rightarrow \texttt{[2,1,2]} \rightarrow \texttt{[4,2,4]} \rightarrow \texttt{[4,2,5]}[0,0,0]→[1,0,0]→[1,0,1]→[2,0,2]→[2,1,2]→[4,2,4]→[4,2,5]。

数据范围

• 1 ≤ nums.length ≤ 10 5 \texttt{1} \le \texttt{nums.length} \le \texttt{10}^\texttt{5}1≤nums.length≤105
• 0 ≤ nums[i] ≤ 10 9 \texttt{0} \le \texttt{nums[i]} \le \texttt{10}^\texttt{9}0≤nums[i]≤109

解法

思路和算法

如果正向计算将arr \textit{arr}arr变成nums \textit{nums}nums的最少函数调用次数，则由于乘法的情况较为复杂，因此需要考虑多种可能的情况。

可以考虑反向操作，每次反向操作可以将数组中的一个元素减1 11或将数组中的所有元素除以2 22，将数组中的所有元素除以2 22的操作只有在所有元素都是偶数的情况下才能执行，计算将nums \textit{nums}nums中的所有元素变成0 00的最少反向操作次数。以下所说的操作均为反向操作。

当数组中存在奇数时，只能将数组中的一个元素减1 11，不能将数组中的所有元素除以2 22。当数组中全部都是偶数时，可以将数组中的一个元素减1 11或将数组中的所有元素除以2 22，为了将函数调用次数最小化，应将数组中的所有元素除以2 22，理由如下。

1. 由于目标是将数组中的所有元素都变成0 00，因此应该将数组中的大于0 00的元素减少，减1 11和除以2 22的操作都可以将元素减少。

2. 将数组中的所有元素除以2 22可以将数组中的所有大于0 00的元素减少，且每个元素的减少量都大于等于1 11。如果使用减1 11操作，则为了达到同样的效果，需要的操作次数不可能更少。

根据上述分析，可以使用贪心的思想计算最少函数调用次数。

对于整数num \textit{num}num，考虑其二进制表示。如果num \textit{num}num是奇数，则二进制表示的最低位是1 11，减1 11操作等价于将最低位的1 11变成0 00；如果num \textit{num}num是偶数，则二进制表示的最低位是0 00，除以2 22操作等价于一次右移操作。当函数调用次数最少时，每次减1 11操作可以使二进制表示的1 11减少一个且二进制表示的位数不变，每次除以2 22操作可以使二进制表示的位数减1 11且二进制表示的1 11的个数不变，因此减1 11操作的次数等于二进制表示的1 11的个数，除以2 22操作的次数等于二进制表示的位数减1 11（需要将除了最高位以外的每一位通过右移消除，剩下一位时必须使用减1 11操作）。

对于数组nums \textit{nums}nums中的每个数可以分别计算减1 11操作的次数和除以2 22操作的次数。对于整个数组，减1 11操作的次数与除以2 22操作的次数计算如下。

• 由于每次减1 11操作只能作用于一个元素，因此整个数组的减1 11操作的次数等于数组中所有元素的二进制表示的1 11的总数。

• 由于每次除以2 22操作可以作用于所有元素，因此整个数组的除以2 22操作的次数等于数组中最大元素的二进制表示的位数减1 11。对于数组中较小的元素，当其变成0 00之后，除以2 22操作将使该元素保持为0 00。

计算最少函数调用次数的具体做法如下。

1. 遍历数组nums \textit{nums}nums，遍历过程中计算整个数组的减1 11操作的次数，并维护数组的最大元素maxNum \textit{maxNum}maxNum。

2. 遍历结束之后，计算数组的最大元素maxNum \textit{maxNum}maxNum的二进制表示的位数减1 11，作为整个数组的除以2 22操作的次数。

3. 整个数组的减1 11操作的次数与除以2 22操作的次数之和即为最少函数调用次数。

代码

classSolution{publicintminOperations(int[]nums){intop0=0,op1=0;intmaxNum=0;for(intnum:nums){op0+=countOnes(num);maxNum=Math.max(maxNum,num);}while(maxNum>1){maxNum>>=1;op1++;}returnop0+op1;}publicintcountOnes(intnum){intones=0;while(num!=0){num&=num-1;ones++;}returnones;}}

复杂度分析

• 时间复杂度：O ( n log ⁡ m ) O(n \log m)O(nlogm)，其中n nn是数组nums \textit{nums}nums的长度，m mm是数组nums \textit{nums}nums中的最大元素。需要遍历数组nums \textit{nums}nums一次计算每个整数的二进制表示中的1 11的个数，遍历结束之后需要计算最大元素m mm的右移操作次数。对于每个整数计算二进制表示中的1 11的个数的时间不超过O ( log ⁡ m ) O(\log m)O(logm)，计算最大元素m mm的右移操作次数需要O ( log ⁡ m ) O(\log m)O(logm)的时间，因此时间复杂度是O ( n log ⁡ m ) O(n \log m)O(nlogm)。

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