按位与大于零的最大组合

2275。按位与大于零的最大组合

难度：中等

主题：数组、哈希表、位操作、计数

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

• 例如，对于 nums = [1, 5, 3]，按位与等于 1 & 5 & 3 = 1。
• 此外，对于 nums = [7]，按位 AND 为 7。

给你一个正整数候选数组。评估候选数字的每个组合的按位与。候选中的每个数字在每个组合中只能使用一次。

返回最大候选组合的大小，按位与大于大于0。

示例1：

• 输入： 候选人 = [16,17,71,62,12,24,14]
• 输出： 4
• 解释： 组合 [16,17,62,24] 的按位与为 16 & 17 & 62 & 24 = 16 > 0。
  • 组合的大小是4。
  • 可以证明，大小大于 4 的组合的按位与大于 0。
  • 请注意，可能有多个组合具有最大尺寸。
  • 例如，组合 [62,12,24,14] 的按位与为 62 & 12 & 24 & 14 = 8 > 0.

示例2：

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

约束：

• 1 5
• 1 7

提示：

1. 要使按位 AND 大于零，组合中的每个数字至少有一位为 1。
2. 候选者有 24 位长，因此对于每个位位置，我们可以计算最大组合的大小，这样按位 AND 将在该位位置得到 1。

解决方案：

我们需要专注于识别数字组，其中二进制表示中至少有一位位置在组合中的所有数字中保持设置 (1)。

解决方案概要

1. 位分析：由于candidates中的每个数字都可以用最多24位的二进制数表示（如1

2. 计算每个位置的设置位：对于每个位位置，计算候选中有多少个数字将该位设置为 1。如果多个数字在同一位置共享一个位，则它们可以可能会在该位位置与大于零的按位 AND 形成组合。

3. 查找最大计数：在任何给定位置具有一组位的数字的最大数量将是答案，因为它代表按位与结果大于的最大可能组合零。

例子

考虑候选人 = [16, 17, 71, 62, 12, 24, 14]:

• 将每个数字转换为二进制并分析位位置。
• 计算所有数字中每个位被设置的次数。
• 找到所有位位置的最大计数。

让我们用 PHP 实现这个解决方案：2275。按位与大于零的最大组合

<?php
/**
 * @param Integer[] $candidates
 * @return Integer
 */
function largestCombination($candidates) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$candidates = [16, 17, 71, 62, 12, 24, 14];
echo largestCombination($candidates); // Output: 4
?>

解释：

1. 循环每个位位置：我们迭代从 0 到 23 的每个位位置。
2. 使用位集计数数字：对于每个位置，计算候选者中有多少个数字具有该特定位集。
3. 更新最大组合大小：跟踪所有位位置的最高计数。
4. 返回结果：根据需要，结果是按位与大于零的最大组合大小。

复杂性分析

• 时间复杂度: O(n x 24) = O(n)，其中 n 是候选中的元素，因为我们对每个数字执行 24 次运算（每个位位置一次）。
• 空间复杂度：O(1)，因为我们只使用固定数量的额外空间。

这种方法足以有效地处理输入大小限制（candidates.length 5）。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是按位与大于零的最大组合的详细内容。更多信息请关注PHP中文网其他相关文章！