针对此Codejam问题,Python中更快或更高内存的解决方案

Question

我尝试了这个Google Codejam Africa问题(比赛已经完成,我只是为了提高我的编程技巧).

问题:

您正在与G客人举办派对,并注意到有奇数客人!在策划派对时,你故意邀请了一对夫妇,并在邀请时给每对夫妇一个唯一的C号.你想通过询问所有客人的邀请号码来挑选出来的人.

输入:

第一行输入给出了案例数,N.N测试案例如下.对于每个测试用例,将有:

• 一行包含值G的客人数量.
• 一行包含以空格分隔的G整数列表.每个整数C表示访客的邀请代码.产量

对于每个测试用例,输出一行包含"Case #x:",后跟单独的guest虚拟机的C号.

限制:

• 1≤N≤50
• 0 <C≤2147483647

小数据集

3≤G<100

大数据集

3≤G<1000

样本输入:

3
3
1 2147483647 2147483647
5
3 4 7 4 3
5
2 10 2 10 5

样本输出:

Case #1: 1
Case #2: 7
Case #3: 5

这是我提出的解决方案:

with open('A-large-practice.in') as f:
    lines = f.readlines()

with open('A-large-practice.out', 'w') as output:
    N = int(lines[0])
    for testcase, i in enumerate(range(1,2*N,2)):
        G = int(lines[i])
        for guest in range(G):
            codes = map(int, lines[i+1].split(' '))
            alone = (c for c in codes if codes.count(c)==1)
        output.write("Case #%d: %d\n" % (testcase+1, alone.next()))

它使用大输入在我的机器上运行12秒.

现在,我的问题是,这个解决方案可以在Python中改进,以便在更短的时间内运行或使用更少的内存吗？对问题的分析给出了关于如何在Java和C++中执行此操作的一些指示,但我无法将这些解决方案转换回Python.

编辑:

结合Alex Martelli和IVlad的提示我现在有这个解决方案,运行在0.079s:

with open('A-large-practice.in') as f:
    lines = f.readlines()

with open('A-large-practice.out', 'w') as output:
    N = int(lines[0])
    for testcase, i in enumerate(range(1,2*N,2)):
        codes = map(int, lines[i+1].split(' '))
        alone = 0
        for c in codes: alone ^= c
        output.write("Case #%d: %d" % (testcase+1, alone))

Answer 1

我不知道python,但问题本身是经典的.给定2K - 1数字,除了一个出现偶数次之外,找到一个出现奇数次的数字.

需要的公式:

1. x xor x == 0 for all x
2. x xor y == y xor x for all x and y
3. x xor (y xor z) == (x xor y) xor z (associativity)
4. x xor 0 == x for all x

所以xor所有的数字.xor-ing所有数字的结果将是你的答案.我不知道你是如何在python中用xor运算符的C语言做的^.

这实际上是最有效的方法,因为您只进行简单的按位操作,甚至不需要存储给定的数字.

您可以检查: 3 ^ 4 ^ 7 ^ 4 ^ 3 == 7,2 ^ 10 ^ 2 ^ 10 ^ 5 == 5等等.