按位与结果大于零的最长组合

标签: 位运算 数组 哈希表 计数

难度: Medium

对数组 nums 执行 按位与 相当于对数组 nums 中的所有整数执行 按位与 。

  • 例如，对 nums = [1, 5, 3] 来说，按位与等于 1 & 5 & 3 = 1 。
  • 同样，对 nums = [7] 而言，按位与等于 7 。

给你一个正整数数组 candidates 。计算 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 <= 105
  • 1 <= candidates[i] <= 107

Submission

运行时间: 280 ms

内存: 25.7 MB

from typing import List

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        max_length = 0
        mask = 0
        
        # 统计 candidates 中每个数字的二进制表示中每一位上 1 的个数
        bit_count = [0] * 32
        for num in candidates:
            for i in range(31, -1, -1):
                if num & (1 << i):
                    bit_count[i] += 1
        
        # 从最高位开始逐位判断，尽量让更多的数字在该位上为 1
        for i in range(31, -1, -1):
            if bit_count[i] > 0:
                mask |= (1 << i)
                max_length = max(max_length, bit_count[i])
        
        return max_length

from typing import List

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        max_length = 0
        
        # 找到 candidates 中的最大值，确定二进制表示的位数
        max_num = max(candidates)
        bits = len(bin(max_num)) - 2
        
        # 从最高位开始逐位判断
        for i in range(bits, -1, -1):
            # 初始化掩码和当前位为1的数字个数
            mask = 1 << i
            count = 0
            
            # 统计当前位为1的数字个数
            for num in candidates:
                if num & mask:
                    count += 1
            
            # 如果当前位为1的数字个数等于数组长度，说明所有数字当前位都为1
            # 直接返回数组长度，因为无法找到更长的组合
            if count == len(candidates):
                return len(candidates)
            
            # 如果当前位为1的数字个数大于0，说明存在组合使得当前位为1
            # 更新最长组合长度，并继续判断下一位
            if count > 0:
                max_length = max(max_length, count)
        
        return max_length

Explain

该题解使用位操作和统计每位上的1的个数来找出按位与结果大于0的最长组合。首先，通过遍历candidates中的所有数字，利用位掩码来检测每个数在每一位上的值（1或0）。然后，统计每一位上1的个数，并存储在一个数组中。之后，从最高位开始逐位判断，找出最大的有效组合长度，即统计出现最多的1的数量，因为这表示最多的数字在此位上可以贡献按位与的结果大于0。整个过程中不需要实际进行组合，只是通过统计每一位的1的数量来确定可能的最长组合长度。

时间复杂度: O(n)

空间复杂度: O(1)

from typing import List

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        max_length = 0 # 初始化最大长度为0
        max_num = max(candidates) # 找到最大的数字以确定位数
        bits = len(bin(max_num)) - 2 # 计算最大数字的位数

        # 从最高位到最低位遍历每一位
        for i in range(bits, -1, -1):
            mask = 1 << i # 创建一个只在第i位上有1的掩码
            count = 0 # 初始化当前位为1的数字个数

            # 统计当前位为1的数字个数
            for num in candidates:
                if num & mask: # 检查数字的第i位是否为1
                    count += 1 # 是则计数增加

            # 更新最长组合长度
            if count > 0: # 只有当存在1时，组合的按位与结果才可能大于0
                max_length = max(max_length, count) # 更新最大长度

        return max_length # 返回最长组合的长度

Explore

在题解中，首先使用`max(candidates)`找出所有候选数字中的最大值，然后通过`len(bin(max_num)) - 2`计算这个最大值的二进制位数。这样做确保了位掩码只会检查每个数字至其最高有效位，因为超出这个范围的高位在所有数字中都是0，不影响结果。通过这种方式，算法避免了不必要的检查和计算，提高了效率。

在这里，'有效组合'是指那些在特定位上至少有一个1的组合，因为只要这个位上至少有一个1，这个组合的按位与结果在该位上就为1，从而使得整个结果大于0。并不是说在所有位上1的数量都必须等于最大组合长度，而是在所有位中选择具有最多1的位，其1的数量就是最大的有效组合长度。

算法通过计数每一位1的数量来估计最长可能的组合长度，是基于这样一个假设：在任何一个位上1的数量越多，表示有更多的数字能在这一位上贡献1，从而使得在这一位上的按位与结果为1。这种方法是一个有效的近似，因为实际上我们只需要找到1的数量最多的位，这就足以保证按位与结果在那一位为1，从而整个结果大于0。

在Python中，`bin()`函数返回的是数字的二进制表示的字符串，其格式为'0b...'，其中'0b'是二进制的前缀。因此，我们需要从总长度中减去2来得到实际的位数。这种方法的潜在问题是，如果最大数字为0，`bin(0)`将返回'0b0'，长度为3，按上述计算方法位数为1，这是正确的。但是，如果不考虑特殊情况，如所有数字都是0，这可能导致不必要的计算。