对阵列的连续子阵列进行异或

1> NPE..：

---

我们不需要枚举(2**n)个子阵列来解决这个问题.

XOR有一些有用的属性,我们可以利用它来在O(n)时间内解决这个问题.特别:

任何k:k XOR k == 0;

任何k:k XOR 0 == k.

XOR是可交换的和关联的.

要解决您的问题,我们首先需要计算每个元素在子数组中出现的次数.出现偶数次的任何元素都可以忽略不计.其余的需要一起进行异或(每次只需一次).

让我们看看这如何适用于您的示例:

1 XOR 2 XOR 3 XOR (1 XOR 2) XOR (2 XOR 3) XOR (1 XOR 2 XOR 3) = # open brackets
1 XOR 2 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3 XOR 1 XOR 2 XOR 3 =       # reorder
1 XOR 1 XOR 1 XOR 2 XOR 2 XOR 2 XOR 2 XOR 3 XOR 3 XOR 3 =       # group
(1 XOR 1 XOR 1) XOR (2 XOR 2 XOR 2 XOR 2) XOR (3 XOR 3 XOR 3) = # remove pairs
1 XOR 0 XOR 3 =
1 XOR 3 =
2

以下是这个想法的O(n)实现:

def xor_em(lst):
  n = len(lst)
  ret = 0
  for i, el in enumerate(lst):
    count = (i + 1) * (n - i)
    if count % 2:
      ret ^= el
  return ret

print xor_em([1, 2, 3])

子阵列的计数是通过

count = (i + 1) * (n - i)

使用观察结果,i + 1当前元素(包括其自身)左侧和n - i右侧(也包括其自身)存在元素.将两者相乘得出从当前元素的左侧开始并且在其右侧结束的子阵列的数量.

我们现在已经将问题减少到寻找对(i + 1)并且(n - i)其产品是奇数的.观察到获得奇数乘积的唯一方法是将两个本身相乘的数相乘(这可以通过考虑两个被乘数的主要因子来看出).

有两种情况需要考虑:

当n为偶数,一个(i + 1)和(n - i)始终是偶数.这意味着对于偶数长度的列表,算法总是返回零.

什么时候n是奇怪的,(i + 1) * (n - i)是奇怪的i = 0, 2, 4, ..., (n - 1).

这导致以下简化的解决方案:

def xor_em(lst):
  if len(lst) % 2 == 0:
    return 0
  else:
    return reduce(operator.xor, lst[::2])

---

+1,编辑修复一个小bug; 希望你不要介意.PS.你真的不需要素数因子分解来证明奇数的乘积是奇数,有点[模运算](https://en.wikipedia.org/wiki/Modular_arithmetic)也会这样做.但我真的不应该抱怨,因为我非常喜欢使用[FTA](https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic)作为一个方便的大锤来解决我自己的问题.:)