用优化方法对具有数组元素的选定元素的XOR操作的最大和

Question

问题:从数组中选择一个元素，以便在XOR数组中的所有元素之后最大化和。

问题陈述输入: N=3 A=15,11,8

产出: 11

方法：(15^15)+(15^11)+(15^8)=11

我的蛮力法代码：

def compute(N,A):
    ans=0
    for i in A:
      xor_sum=0
      for j in A:
        xor_sum+=(i^j)
      if xor_sum>ans:
          ans=xor_sum
    return ans

上面的方法给出了正确的答案，但希望通过优化该方法来解决O(n)时间复杂度问题。请帮我拿这个。

Answer 1

如果有一个固定(常量) c位数的整数，那么它应该是可能的，因为O(c) = O(1)。出于简单的原因，我假设无符号整数和n是奇数。如果n是偶数，那么我们有时必须检查树中的两条路径(参见下面的解决方案)。您可以对算法进行调整，以覆盖偶数n和负数。

1. 在长度为n O(n)

的数组中查找max

如果

1. 返回0(数组中仅为0)，则为

1. 找到max O(c) = O(1)中最重要位的位置p

P= -1而(max != 0) p++ max /= 2

因此，1 << p为最高集位提供了一个掩码。

1. 构建了一棵树，其中叶子是数字，每个级别代表一个位的位置，如果从根到左边有一条边，那么就有一个有位p集的数字，如果右边有一个边，则有一个没有设置位p的数字，对于下一个级别，如果有一个有位p - 1集的数字，则左边有一个边，如果没有设置bit p - 1，则可以在O(cn) = O(n)

中这样做。

1. 遍历数组并计算在I位置(i从0到p)设置了多少次=> sum数组O(cn) = O(n)

将树根分配给节点x的

1. 现在对从p到0的每个i执行以下操作：

1. if `x` has only one edge => `x` becomes its only child node
2. else if `sum[i]` > `n / 2` => `x` becomes its right child node
3. else `x` becomes its left child node

在这一步中，我们通过树选择最佳路径，当O(cn) = O(n)时，树给出的路径最多。

1. xor数组中所有元素的值为x，并对它们进行求和以得到结果，实际上，您本来可以在步骤中构建结果，方法是将sum[i] * (1 << i)添加到左转，将(n - sum[i]) * (1 << i)添加到右O(n)

所有的顺序步骤都是O(n)，因此整个算法也是O(n)。