文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题得到目标数组的最少函数调用次数出处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}1225。示例 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}213。示例 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≤1050 ≤ 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理由如下。由于目标是将数组中的所有元素都变成0 00因此应该将数组中的大于0 00的元素减少减1 11和除以2 22的操作都可以将元素减少。将数组中的所有元素除以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。计算最少函数调用次数的具体做法如下。遍历数组nums \textit{nums}nums遍历过程中计算整个数组的减1 11操作的次数并维护数组的最大元素maxNum \textit{maxNum}maxNum。遍历结束之后计算数组的最大元素maxNum \textit{maxNum}maxNum的二进制表示的位数减1 11作为整个数组的除以2 22操作的次数。整个数组的减1 11操作的次数与除以2 22操作的次数之和即为最少函数调用次数。代码classSolution{publicintminOperations(int[]nums){intop00,op10;intmaxNum0;for(intnum:nums){op0countOnes(num);maxNumMath.max(maxNum,num);}while(maxNum1){maxNum1;op1;}returnop0op1;}publicintcountOnes(intnum){intones0;while(num!0){numnum-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)。