在 Python 中查詢與陣列中每個整數進行異或運算時，能使異或和最小化的數字

假設我們有一個數組 A，我們需要找到一個數字 X，使得 (A[0] XOR X) + (A[1] XOR X) + … + A[n – 1] XOR X 的值儘可能小。

因此，如果輸入類似於 [3, 4, 5, 6, 7]，則輸出將是 X = 7，Sum = 10

為了解決這個問題，我們將遵循以下步驟：

• 定義一個函式 search_res()。它將接收陣列 arr 和陣列大小 n 作為引數。
• element := arr[0]
• 對於 i 從 0 到陣列大小，執行以下操作：
  • 如果 arr[i] > element，則
    • element := arr[i]
• p := element 以 2 為底的對數的整數部分 + 1
• X := 0
• 對於 i 從 0 到 p，執行以下操作：
  • cnt := 0
  • 對於 j 從 0 到 n，執行以下操作：
    • 如果 arr[j] AND (2^i) 不為零，則
      • cnt := cnt + 1
  • 如果 cnt > n / 2 的整數部分不為零，則
    • X := X + (2^i)
• sum := 0
• 對於 i 從 0 到 n，執行以下操作：
  • sum := sum +(X XOR arr[i])
• 返回 X 和 sum

示例

讓我們看下面的實現來更好地理解：

from math import log2
def search_res(arr, n):
   element = arr[0]
   for i in range(len(arr)):
      if(arr[i] > element):
         element = arr[i]
   p = int(log2(element)) + 1
   X = 0
   for i in range(p):
      cnt = 0
      for j in range(n):
         if (arr[j] & (1 << i)):
            cnt += 1
      if (cnt > int(n / 2)):
         X += 1 << i
   sum = 0
   for i in range(n):
      sum += (X ^ arr[i])
   print("X =", X, ", Sum =", sum)
arr = [3, 4, 5, 6, 7]
n = len(arr)
search_res(arr, n)

輸入

[3, 4, 5, 6, 7]

輸出

X = 7 , Sum = 10

Arnab Chakraborty

更新於： 2020-08-28

83 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始