Medium

题目描述

数组 nums 的按位与结果是 nums 中所有整数的按位与。

  • 例如，对于 nums = [1, 5, 3]，按位与结果等于 1 & 5 & 3 = 1。
  • 又例如，对于 nums = [7]，按位与结果是 7。

给你一个正整数数组 candidates。计算 candidates 中的元素任意组合的按位与结果。

返回按位与结果大于 0 的最大组合的大小。

示例 1：

输入：candidates = [16,17,71,62,12,24,14]
输出：4
解释：组合 [16,17,62,24] 的按位与结果是 16 & 17 & 62 & 24 = 16 > 0 。
组合的大小是 4 。
可以证明不存在按位与结果大于 0 且大小超过 4 的组合。
注意，符合条件的组合可能不止一个。
例如，组合 [62,12,24,14] 的按位与结果是 62 & 12 & 24 & 14 = 8 > 0 。

示例 2：

输入：candidates = [8,8]
输出：2
解释：最大组合 [8,8] 的按位与结果是 8 & 8 = 8 > 0 。
组合的大小是 2 ，所以我们返回 2 。

提示：

  • 1 <= candidates.length <= 10^5
  • 1 <= candidates[i] <= 10^7

解题思路

解题思路

要使按位与结果大于0，至少需要有一位在所有选中的数字中都是1。这给了我们一个关键洞察：我们可以按位来考虑这个问题。

核心观察：

  1. 按位与运算的特点是，只有当所有数字在某一位都是1时，结果在该位才是1
  2. 要使最终结果大于0，至少需要有一位在所有选中数字中都是1
  3. 因此，问题转化为：找到某一位，使得在该位上为1的数字个数最多

算法步骤：

  1. 遍历所有可能的位（从第0位到第23位，因为最大值是10^7 < 2^24）
  2. 对于每一位，统计有多少个数字在该位上是1
  3. 返回所有位中的最大计数值

这种方法的正确性在于：如果我们选择所有在第i位为1的数字组成组合，那么这个组合的按位与结果在第i位必然是1，因此结果大于0。而我们要找的是最大的这样的组合。

时间复杂度分析： 需要检查24位，每位需要遍历n个数字，所以总时间复杂度是O(24n) = O(n)。

空间复杂度分析： 只使用了常数额外空间，所以空间复杂度是O(1)。

代码实现

class Solution {
public:
    int largestCombination(vector<int>& candidates) {
        int maxSize = 0;
        
        // 检查每一位（0到23位足够覆盖10^7）
        for (int bit = 0; bit < 24; bit++) {
            int count = 0;
            
            // 统计在当前位为1的数字个数
            for (int num : candidates) {
                if (num & (1 << bit)) {
                    count++;
                }
            }
            
            maxSize = max(maxSize, count);
        }
        
        return maxSize;
    }
};

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        max_size = 0
        
        # 检查每一位（0到23位足够覆盖10^7）
        for bit in range(24):
            count = 0
            
            # 统计在当前位为1的数字个数
            for num in candidates:
                if num & (1 << bit):
                    count += 1
            
            max_size = max(max_size, count)
        
        return max_size

public class Solution {
    public int LargestCombination(int[] candidates) {
        int maxSize = 0;
        
        // 检查每一位（0到23位足够覆盖10^7）
        for (int bit = 0; bit < 24; bit++) {
            int count = 0;
            
            // 统计在当前位为1的数字个数
            foreach (int num in candidates) {
                if ((num & (1 << bit)) != 0) {
                    count++;
                }
            }
            
            maxSize = Math.Max(maxSize, count);
        }
        
        return maxSize;
    }
}

/**
 * @param {number[]} candidates
 * @return {number}
 */
var largestCombination = function(candidates) {
    let maxSize = 0;
    
    // 检查每一位（0到23位足够覆盖10^7）
    for (let bit = 0; bit < 24; bit++) {
        let count = 0;
        
        // 统计在当前位为1的数字个数
        for (let num of candidates) {
            if (num & (1 << bit)) {
                count++;
            }
        }
        
        maxSize = Math.max(maxSize, count);
    }
    
    return maxSize;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要检查24位，每位遍历n个数字，24为常数
空间复杂度O(1)只使用常数额外空间

相关题目