偶-偶或奇偶对的异或大于4

Question

给定一个偶数和奇数数组，我想要得到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

编辑:我发现了一些东西。任何在% 4之后给出余数的数字x，即x%4 != 0，当XORed为数字-2本身时，结果将为2。例如，6。它不能被4整除，因此，6异或6-2 ( 4 )，==> 2。10不能被4整除，因此，10异或10-2 (8) ==> 2。你能告诉我这如何帮助我优化我的代码吗？我现在只知道，我将只查找可被4整除的数字，并找到它们的+ 2的计数。

Answer 1

为了简单起见，我们假设数组没有重复项。对于2个数字之间的异或运算为>= 4，它们需要有任何不同的位(不包括低2位)。假设我们已经知道它们是偶-偶或奇-偶对，那么它们的最低位是相同的。

请注意，对于任何数字X，XOR (X + 4 + k)将始终是>= 4。因此，问题是考虑X XOR (X + 1)、X XOR (X + 2)和X XOR (X + 3)会发生什么。当第三个最低的位只加1时，XOR (X + 1)将是>= 4。这意味着，我们有X以011结束，所以X+1以100结束，或者我们有X以111结束，所以X+1以000结束。在这两种情况下，这意味着X%4= 3。在任何其他情况下(X%4 != 3)，XOR (X + 1)将小于4。

对于XOR (X + 2)为>= 4，第三个最低位已通过添加2而更改。这意味着，X以011、010、111或110结尾。所以我们现在有X%4=3或X%4= 2。

对于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个数字的数量)

Answer 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

Answer 3

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

复杂性：

假设您的dictionaries ( hashmap)有一个很好的hash function，平均时间复杂度为O(n)