題目連結:
題目意譯:
一個陣列 nums 的按位元(Bitwise)之 AND 操作為 nums 中所有整數的按位元 AND 之結果。
例如說,對於 nums = [1, 5, 3],按位元 AND 之值等於 1 & 5 & 3 = 1。
而對於 nums = [1, 5, 3],按位元 AND 之值等於 7。
你被給定一正整數陣列 candidates。請對 candidates 的每一種組合求出按位元 AND 之值。candidates 中每一個數字在一個組合中只能使用一次。
回傳有著按位元 AND 之值大於 0 的 candidates 組合之最大的大小為何。
限制:
1 ≦ candidates.length ≦ 10 ^ 5
1 ≦ candidates[i] ≦ 10 ^ 7
範例測資:
範例 1:
輸入: candidates = [16,17,71,62,12,24,14]
輸出: 4
解釋: 組合 [16,17,62,24] 有著按位元 AND 之值 16 & 17 & 62 & 24 = 16 > 0。
該組合的大小為 4。
可以證明沒有其他組合有著大小大於 4 並且滿足按位元 AND 之值大於 0。
注意到可能有多於一個組合有著最大的大小。
例如說,組合 [62,12,24,14] 有著按位元 AND 之值 62 & 12 & 24 & 12 = 8 > 0。
範例 2:
輸入: candidates = [8,8]
輸出: 2
解釋: 最大的組合 [8,8] 有著按位元 AND 之值 8 & 8 = 8 > 0。
該組合的大小為 2,所以我們回傳 2。
解題思維:
掃過 candidates 中所有數字並用一個陣列來統計對於每個位元(2 ^ i)有多少數字的二進位表示法中第 i 個位元為「1」。
接著掃過每一個位元,看哪個位元的統計值最大即為所求(代表我們只要挑該位元對應的原先那些數字 AND 之後便保證 > 0)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。