Medium

题目描述

给你一个整数数组 nums。你有一个长度相同的整数数组 arr，其所有值最初都设为 0。你还有以下修改函数：

你可以调用函数使 arr 中任意一个元素加 1。 你可以调用函数使 arr 中所有元素同时乘 2。

你想要使用最少的函数调用次数将 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](目标数组)。

约束：

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

提示：

  • 反向思考：尝试从 nums 到 arr
  • 尽可能多地除以 2，但只有当所有元素都是偶数时才能除以 2

解题思路

这题的关键是反向思考：从目标数组 nums 逆向推导到全 0 数组 arr。

核心思路是贪心算法：

  1. 除法操作：当数组中所有非零元素都是偶数时，我们可以将整个数组除以 2（相当于正向的乘 2 操作）
  2. 减法操作：对于奇数元素，我们必须先减 1 使其变为偶数（相当于正向的加 1 操作）

算法步骤：

  1. 统计所有元素的 1 的个数（即需要的减法操作次数）
  2. 找到数组中最大元素的二进制位数，这决定了最多需要多少次除法操作
  3. 不断检查数组是否全为 0：
    • 如果有奇数，将其减 1
    • 如果所有非零元素都是偶数，将所有元素除以 2

优化思路：我们可以直接通过位操作来计算：

  • 加法操作次数 = 所有数字二进制表示中 1 的总个数
  • 乘法操作次数 = 最大数字的二进制位数减 1（因为最后一步不需要乘 2）

这样可以避免模拟整个过程，直接得出答案。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int addOps = 0;  // 加法操作次数
        int maxBits = 0; // 最大数字的位数
        
        for (int num : nums) {
            if (num == 0) continue;
            
            // 统计1的个数（加法操作）
            addOps += __builtin_popcount(num);
            
            // 找最大数字的位数
            int bits = 32 - __builtin_clz(num);
            maxBits = max(maxBits, bits);
        }
        
        // 乘法操作次数 = 最大位数 - 1
        int mulOps = maxBits > 0 ? maxBits - 1 : 0;
        
        return addOps + mulOps;
    }
};

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        add_ops = 0  # 加法操作次数
        max_bits = 0  # 最大数字的位数
        
        for num in nums:
            if num == 0:
                continue
                
            # 统计1的个数（加法操作）
            add_ops += bin(num).count('1')
            
            # 找最大数字的位数
            bits = num.bit_length()
            max_bits = max(max_bits, bits)
        
        # 乘法操作次数 = 最大位数 - 1
        mul_ops = max_bits - 1 if max_bits > 0 else 0
        
        return add_ops + mul_ops

public class Solution {
    public int MinOperations(int[] nums) {
        int addOps = 0;  // 加法操作次数
        int maxBits = 0; // 最大数字的位数
        
        foreach (int num in nums) {
            if (num == 0) continue;
            
            // 统计1的个数（加法操作）
            addOps += CountBits(num);
            
            // 找最大数字的位数
            int bits = (int)Math.Floor(Math.Log2(num)) + 1;
            maxBits = Math.Max(maxBits, bits);
        }
        
        // 乘法操作次数 = 最大位数 - 1
        int mulOps = maxBits > 0 ? maxBits - 1 : 0;
        
        return addOps + mulOps;
    }
    
    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function(nums) {
    let operations = 0;
    let maxBits = 0;
    
    for (let num of nums) {
        let bits = 0;
        let temp = num;
        
        while (temp > 0) {
            if (temp & 1) {
                operations++;
            }
            temp >>= 1;
            bits++;
        }
        
        maxBits = Math.max(maxBits, bits);
    }
    
    return operations + Math.max(0, maxBits - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n × log M)n 为数组长度，M 为数组中最大值，需要统计每个数的二进制位
空间复杂度O(1)只使用常数额外空间