在 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

更新于： 2020-08-28

83 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告