給你一個陣列 A。你必須從這個陣列中選擇一個元素，比如 A[k] 并形成一個新的陣列 B，使得 B[i] = A[i]^A[k]。（^ 表示按位異或）。
現在陣列的分數將是 B 的所有元素的總和。
任務是找到陣列分數最大的元素。
示例 -如果 A = [15,11,8]
并且
我們選擇 A[k] = 15 那么 B 將是 [0,4,7] (15^15=0,15^11=4,15^8=7 ）。分數將是 0 4 7 = 11，這是我們通過選擇任何元素作為 A[k] 可以獲得的最大值。
另一個例子 -
如果 A = [11,12,13,14,15] 最大可能分數 = 22。
我們如何解決這個問題來選擇一個產生最高分數的元素。
如何解決這個問題或如何處理這些問題？
uj5u.com熱心網友回復：
許多異或演算法問題的答案是一點一點地作業。在這里，如果對于每個位位置，您計算設定了該位的陣列元素的數量（順便告訴您通過從陣列長度中減去多少陣列元素沒有設定該位），您有一種快速計算的方法sum(A[i] xor X)對于任何X，通過考慮每個可能位貢獻的總和部分。這種計算和的方式取決于陣列中最大數的位寬，而不是陣列的長度。
完成此操作后，您可以簡單地遍歷陣列并找到使總和最大化的元素。
如果你做對了，那么演算法是 O(NW)，其中 N 是輸入陣列的長度，W 是最小的數字，使得每個輸入數字都適合 W 位整數。它會使用 O(W) 額外的存盤空間。（通常，這些演算法問題會限制輸入的大小，因此它們適合 int32 或 int64，因此 W 將是 32 或 64）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/427017.html
下一篇：埃拉托色尼篩改進后運行速度變慢