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

概述我尝试了这个 Google Codejam Africa问题(比赛已经完成,我只是为了提高我的编程技巧). The Problem: You are hosting a party with G guests and notice that there is an odd number of guests! When planning the party you deliberately invi 我尝试了这个 Google Codejam Africa问题(比赛已经完成,我只是为了提高我的编程技巧).

The Problem:

You are hosting a party with G guests
and notice that there is an odd number
of guests! When planning the party you
deliberately invited only couples and
gave each couple a unique number C on
their invitation. You would like to
single out whoever came alone by
asking all of the guests for their
invitation numbers.

The input:

The first line of input gives the number of cases,N.
N test cases follow. For each test case there will be:

One line containing the value G the
number of guests. One line containing
a space-separated List of G integers.
Each integer C indicates the
invitation code of a guest. Output

For each test case,output one line
containing “Case #x: ” followed by the
number C of the guest who is alone.

The limits:

1 ≤ N ≤ 50 0 < C ≤ 2147483647

Small dataset

3 ≤ G < 100

Large dataset

3 ≤ G < 1000

样本输入：

331 2147483647 214748364753 4 7 4 352 10 2 10 5

样本输出：

Case #1: 1Case #2: 7Case #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()))

它使用large input在我的机器上运行12秒.

现在,我的问题是,这个解决方案可以在Python中改进,以便在更短的时间内运行或使用更少的内存吗？该问题的analysis提供了一些关于如何在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',2)):        codes = map(int,lines[i+1].split(' '))        alone = 0        for c in codes: alone ^= c        output.write("Case #%d: %d" % (testcase+1,alone))

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

需要的公式：

对于所有x,> x xor x == 0
> x xor y == y xor x表示所有x和y
> x xor(y xor z)==(x xor y)xor z(关联性)
> x xor 0 == x表示所有x

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

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

你可以检查：3 ^ 4 ^ 7 ^ 4 ^ 3 == 7,2 ^ 10 ^ 2 ^ 10 ^ 5 == 5等

总结

以上是内存溢出为你收集整理的针对此Codejam问题,Python中更快或更高内存的解决方案全部内容，希望文章能够帮你解决针对此Codejam问题,Python中更快或更高内存的解决方案所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。