按位與大於零的最大組合

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中文網其他相關文章！