给定偶数和奇数的数组，我想得到其XOR大于或等于4的（偶数偶数）和（奇数 - 奇数）对的数量。我尝试使用下面的代码，但它在O中运行（n ^ 2），（yikes）。请问任何人都可以建议一种优化方法吗？
n = int(raw_input()) #array size
ar = map(int, raw_input().split()) #the array
cnt = 0
for i in xrange(len(ar)):
for j in xrange(i+1, len(ar)):
if ar[i] ^ ar[j] >= 4 and (not ar[i] & 1 and not ar[j] & 1):
cnt += 1; #print ar[i],ar[j],ar[i]^ar[j];
elif ar[i] ^ ar[j] >= 4 and (ar[i] & 1 and ar[j] & 1):
cnt += 1
print cnt
编辑：我发现了一些东西。任何数字x，它给出％4之后的余数，即x％4！= 0，当XOR到数字-2本身时将得到2。例如，6。它不能被4整除，因此，6 XOR 6-2（4），==> 2. 10不能被4整除，因此，10 XOR 10-2（8）==> 2。你能告诉我这有助于我优化代码吗？我现在才知道我只会查找可被4整除的数字，并找到他们的+2的数量。
为简单起见，假设数组没有重复项。对于2个数之间的XOR> = 4，它们需要具有任何不同的位（不包括低2位）。鉴于我们已经知道它们是偶数偶数或奇数对，它们的最低位是相同的。
请注意，对于任何数字X，X XOR（X + 4 + k）将始终> = 4.因此问题是考虑X XOR（X + 1），X XOR（X + 2）和X XOR（ X + 3）。 X XOR（X + 1）将> = 4当第三个最低位通过仅添加1而改变时。这意味着，我们将X结束于011，因此X + 1以100结尾或者我们将X结束于111，因此X +在两种情况下，这意味着X％4 = 3.在任何其他情况下（X％4！= 3），X XOR（X + 1）将<4。
对于X XOR（X + 2）> = 4，第三个最低位通过加2来改变。这意味着，X以011,010,111或110结束。所以我们现在有X％4 = 3或X ％4 = 2。
对于X Xor（X + 3）> = 4，第三个最低位通过加3而改变。这意味着，X以011,010,001,111,110,101结束。所以我们现在有X％4 = 3，X％4 = 2或X％4 = 1。
这是伪代码：
for each element in array:
count[element] += 1
total += 1
for each X in sorted keys of count:
if X % 4 == 3:
answer += count[X + 1] + count[X + 2] + count[X + 3]
if X % 4 == 2:
answer += count[X + 2] + count[X + 3]
if X % 4 == 1:
answer += count[X + 3]
total -= count[X]
answer += total - (count[X + 1] + count[X + 2] + count[X + 3]) # all X + 4 + K work
为了解决重复问题，我们需要避免对自己计算一个数字。您将需要保留每个数字的计数，并执行与上述相同的修改，答案将是该数字的计数*（所有其他数字 - X + 2个数字的数量）
您应该努力分离您的代码，一个改进是使用set来避免重复操作，尽管它可能会获得更多的内存开销。
import random
from operator import xor
import itertools
random.seed(10)
in_values = [random.randint(0, 10) for _ in range(100)]
def get_pairs_by(condition, values):
odds = set(filter(lambda x: x % 2 == 0, values))
evens = set(filter(lambda x: x % 2 == 1, values))
def filter_pairs_by_condition(values):
return (
(x, y) for x, y in set(
map(lambda x: tuple(sorted(x)),
itertools.product(iter(values), iter(values))))
if condition(xor(x, y))
)
return list(
itertools.chain.from_iterable(
(filter_pairs_by_condition(x) for x in (odds, evens))
)
)
print(get_pairs_by(lambda x: x >= 4, in_values))
关键点是：
set(map(lambda x: tuple(sorted(x)),
itertools.product(iter(values), iter(values)))))
我们正在做的是（5,7）和（7,5）对应该被评估为相同，所以我们在那里去掉它们。
在这里你有live example
编辑：作为代码的快速更新，您可以使用字典来记忆先前计算的对，因此：
n = int(raw_input()) #array size
ar = map(int, raw_input().split()) #the array
cnt = 0
prev_computed = {}
for i in xrange(len(ar)):
for j in xrange(i+1, len(ar)):
if any(x in prev_compued for x in ((ar[i], ar[j]), (ar[j], ar[i]))):
cnt += 1
continue
if ar[i] ^ ar[j] >= 4 and (not ar[i] & 1 and not ar[j] & 1):
cnt += 1; #print ar[i],ar[j],ar[i]^ar[j];
prev_computed[(ar[i], ar[j])] = True
prev_computed[(ar[j], ar[i])] = True
elif ar[i] ^ ar[j] >= 4 and (ar[i] & 1 and ar[j] & 1):
cnt += 1
prev_computed[(ar[i], ar[j])] = True
prev_computed[(ar[j], ar[i])] = True
print cnt
def xor_sum(lst)
even_dict = a dictionary with keys being all even numbers of lst and values being their frequencies
odd_dict = a dictionary with keys being all odd numbers of lst and values being their frequencies
total_even_freq = sum of all frequencies of even numbers
total_odd_freq = sum of all frequencies of odd numbers
even_res = process(even_dict, total_even_freq)
odd_res = process(odd_dict, total_odd_freq)
return even_res + odd_res
def process(dict, total_freq)
res = 0
for num in dict.keys
# LSB of XOR of 2 even numbers is always 0
# Let p = XOR of 2 even numbers; if p < 4 then p = 00000000 (minus_2) or 00000010 (plus_2)
plus_2 = num+2
minus_2 = num-2
count = 0
if( (plus_2 XOR num) < 4 and (plus_2 is a key of dict) )
count = count + frequency_of_plus_2
if( (minus_2 XOR num) < 4 and (minus_2 is a key of dict) )
count = count + frequency_of_minus_2
count = count + num
res = res + (total_freq+1-count)
return res
复杂：
假设你的hash function（dictionaries）有一个很好的hashmap，平均时间复杂度是O(n)