针对 Codejam 问题的 Python 更快或更高效的解决方案

Question

我尝试了这个 Google Codejam Africa< /a> 问题（比赛已经结束，我只是为了提高我的编程技能）。

问题：

您正在与 G 位客人举办派对 并注意有一个奇数 的客人！当您计划聚会时 特意只邀请情侣和 给每对夫妇一个独特的数字C 他们的邀请。你愿意 挑出单独过来的人 询问所有客人的情况 邀请号码。

输入：

输入的第一行给出案例数 N。 接下来是 N 个测试用例。对于每个测试用例，将有：

• 一行包含值 G 客人人数。
• 一行包含 以空格分隔的 G 整数列表。 每个整数C表示 客人的邀请码。输出

对于每个测试用例，输出一行 包含“Case #x:”，后跟 独自一人的客人的号码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.079 秒的解决方案：

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 对于所有 x
2. x xor y == y xor x 对于所有 x 和 y
3. x xor (y xor z) = = (x xor y) xor z（关联性）
4. x xor 0 == x 对于所有 x

所以 异或所有数字。对所有数字进行异或运算的结果就是您的答案。我不知道如何在 python 中执行此操作，在 C 语言中，异或运算符是 ^。

这确实是最有效的方法，因为您只需执行简单的按位运算，甚至不必存储给定的数字。

您可以检查：
3 ^ 4 ^ 7 ^ 4 ^ 3 == 7，2 ^ 10 ^ 2 ^ 10 ^ 5 == 5等。

Answer 2

我的机器比你的慢——你的代码（放入 main 函数）在我的机器上花了 19 秒。删除无用的内部 for 的明显优化将其缩短为 0.46 秒；更改代码的核心以将

      alone = 0
      for c in codes: alone ^= c

时间缩短至 0.08 秒。我确信进一步的优化是可能的，但由于代码已经快了 235 倍，我认为这可能就足够了；-)。

Answer 3

考虑一下：

codes = map(int, lines[i+1].split(' '))

为什么要为 guest 的每个值重新分割行？线路不会改变。

另外，请考虑这一点：

for guest in range(G):
    codes = map(int, lines[i+1].split(' '))
    alone = (c for c in codes if codes.count(c)==1)

此循环中的所有代码都不依赖于 guest。为什么是循环呢？

Answer 4

这对我来说立即完成并得到相同的结果：

src = open('A-large-practice.in')
dst = open('A-large-practice.out', 'w')

n = int(src.readline().rstrip())
for i in xrange(n):
    src.readline() # skip g
    nums = src.readline().split()
    seen = set()
    for n in nums:
        if n in seen:
            seen.remove(n)
        else:
            seen.add(n)
    dst.write("Case #%d: %s\n" % (i+1, tuple(seen)[0]))

src.close()
dst.close()

该死，我喜欢哈希映射！

Answer 5

是的，正如分析页面所解释的，您可以使用常量内存，尽管任何方法都将在 O(n) 时间内运行。以下是常量内存解决方案在 Python 中的工作原理：

numbers = [1, 1, 2, 2, 3, 3, 4, 4, 12345]
missingOne = 0
for number in numbers:
    missingOne = missingOne ^ number
assert missingOne == 12345

关键是理解异或运算符的作用。任何与零进行异或的数字都是其本身。任何与自身异或的数字都是零。如果您查看异或的真值表，您应该能够使自己相信这两个事实，然后证明从零开始对列表中的数字进行异或将产生不重复的数字。