我的问题是 SPOJ 问题的“超出时间限制”错误。我认为这个错误是因为输入量大,所以我需要你的帮助来找到处理大输入量的最佳方法。
让我解释一下输入和我的代码。
Input
The first line of the input contains test cases t(1<=t<=100). It is followed by 2*t lines, 2 for each test case. The first line of input for each test case contains a number n (0<=n<=10^6), followed by n elements in the next line. Each number is from -10^3 to +10^3
这里是输入的例子
3 #number of test cases (t)
4 #number of elements that will come to next line (n) (this can be 10^6)
2 1 2 2 #this line may have 10^6 numbers
6
1 1 1 2 2 2
5
1 2 4 5 1
问题是询问一个数字是否出现超过 n//2 次。 示例输出
YES 2 #because 2 appears 3 times.
NO # no number occurs more than n//2 times
NO # no number occurs more than n//2 times.
关于问题的更多信息
Added by: Troika::Bytes Date: 2010-02-18 Time limit: 1s Source limit: 50000B Memory limit: 256MB Cluster: Pyramid (Intel Pentium III 733 MHz) Languages: All except: PERL 6
http://www.spoj.com/problems/MAJOR/
最后是我的代码。
from collections import Counter
import re
def major(n):
s = input().split() # get all the numbers one by one
y = (Counter(s)).most_common()[0] # Count how many times a number occurs in the input and return the most occurence with its value in a pair.
if y[1]> n//2: #if the most occurence is more than half of the "n"
return "YES " + y[0] # return the value belongs to the most occurence
else:
return "NO"
for i in range(int(input())): #get the number of test cases
print(major(int(input()))) # calling the function to get the "n"
在想知道 s = input().split() 对于像一百万个数字来说可能太慢了。 但是,我再次收到“超出时间限制”的错误。会不会跟Counter函数有关?
请您参考如下方法:
您可以通过以下方式对其进行优化:
禁用垃圾回收:
import gc gc.disable()避免使用
string.split并使用re.finditer。避免使用
range并使用 while 循环。使用
sys.stdin.readline()代替input(速度更快)和sys.stdout.writeintead打印量。当数字的出现次数大于
n//2时停止(另外,只计算一次)。您可以使用collections.defaultdict并在更新前检查出现的次数。避免使用函数,将所有内容放在一个循环中。
有时在
main函数中导入库可以节省时间。
不幸的是Martijn Pieters注意,Python 3.x 没有公认的解决方案而且只有一个 Python 2.x ,并且根据解决它所花费的内存量,numerix 可以使用 psyco(PyPy 所基于的库,比 CPython 快得多)。不幸的是,由于 psyco 已经停止,它的支持已经在集群上被删除,问题被执行,所以可能没有人会设法发送接受的解决方案,直到他们重新启用 psyco 或 PyPy 支持。
例子
import gc
gc.disable()
# import psyco
# psyco.full()
def main():
from collections import defaultdict
from sys import stdin, stdout
import re
pattern = re.compile(r'\d+')
times = int(stdin.readline())
while times:
times -= 1
threshold = int(stdin.readline()) // 2
vals = defaultdict(int)
for x in pattern.finditer(stdin.readline()):
n = int(x.group(0))
rep = vals[n] + 1
if rep > threshold:
stdout.write('YES ' + str(n) + '\n')
break
else:
vals[n] = rep
else:
stdout.write('NO\n')
if __name__ == '__main__':
main()
编辑
我给 numerix 发了一封电子邮件,他确认他的解决方案使用了 psyco:
Yes, my solution for MAJOR uses psyco. I didn't try without psyco, but as there is no other AC Python solution I guess it won't be possible or only with heavy i/o optimization.
