如何提高python-cod的运行时间

Question

我试图从一个在线编码网站解决下面的问题。在

问题： 弗雷多很擅长处理大量数据。所以，有一次他的朋友宙斯给了他一个N个数的数组，然后是他必须回答的Q问题。在每个查询中，他定义了查询的类型和Fredo必须回答的数字f。每个查询都有以下两种类型： 类型0：对于这个查询，Fredo必须回答数组中的第一个数字（从索引0开始），使其频率至少等于f。 类型1：对于这个查询，Fredo必须回答数组中的第一个数字，以便frequecy正好等于f。 现在，弗雷多回答了他所有的问题，但现在宙斯想象他应该如何验证这些问题。所以，他让你写一个代码。 注意：如果没有数字作为查询的答案，则输出0。 使用快速I/O

输入： 输入的第一行包含N，即数组的大小 下一行包含N个空格分隔的整数。 下一行包含Q，表示查询的数量。 然后跟随Q行，每行有两个整数type和f，表示查询的类型和回答查询的频率。在

输出： 您必须在单独的行中打印每个查询的答案。在

输入约束：

1≤N≤106

1≤A[i]≤1018

1≤Q≤106

0≤类型≤1

1≤f≤1018

样本输入

六

1 2 2 1 2 3

五

0 1

0 2个

12个

13个

0 3个

样本输出

1

1

1

二

二

解决方案： 这是我尝试过的解决方案

from collections import Counter
import sys
tokenizedInput = sys.stdin.read().split()
t = int(tokenizedInput[0])
a = []
for i in range(t):
    s = int(tokenizedInput[i+1])
    a.append(s)
collection = Counter(a)
key = collection.keys()
value = collection.values()
q = int(tokenizedInput[i+2])
k = i+2
for j in range(q):
    query = int(tokenizedInput[k+2*j+1])
    f = int(tokenizedInput[k+2*j+2])
    for w in range(t):
        index = key.index(a[w])
        if query == 0:
            if value[index] >= f:
                print a[w]
                break
        else:
            if value[index] == f:
                print a[w]
                break
        if w == t-1:
            print 0

这段代码可以正常运行，并为较小的测试用例提供正确的输出，但是对于较大的测试用例，它会超过时间限制。有人可以建议对这段代码做些什么改进来提高速度吗。在

Answer 1

一些建议：完成tokenizedInput的int()转换，而不是在循环中一遍又一遍地调用int()；像{}这样的字典非常有效，不要通过提取键和值来猜测它，而是按预期使用它；在循环之前预先计算出任何你能计算的东西；简化，简化，简化。在

我已经按照上面的建议重新编写了您的代码，再加上其他一些调整，看看它对您是否有意义，并在时间限制内执行该练习：

import sys
from collections import Counter

tokenizedInput = map(int, sys.stdin.read().split())

N = tokenizedInput[0]

array = tokenizedInput[1:N + 1]

collection = Counter(array)

Q = tokenizedInput[N + 1]

k = N + 2

for j in range(Q):
    offset = 2 * j + k
    query, frequency = tokenizedInput[offset:offset + 2]

    for w in range(N):
        value = collection[array[w]]

        if query == 0:
            if value >= frequency:
                print array[w]
                break
        else:
            if value == frequency:
                print array[w]
                break

    else:  # aka "no break"
        print 0

大多数人都会用单独的read语句来输入各种标量和数组值来处理这个问题。你在一开始就选择了一次阅读，这很好，但是你必须在你的设计中注意，最初的选择不会妨碍你以后的发展。在