我正在Find the min使用 python 在 facebook hackercup 上解决问题，我的代码适用于示例输入，但对于大型输入（10^9），它需要几个小时才能完成。
那么，是否有可能使用 python 无法在 6 分钟内计算出该问题的解决方案？或者可能是我的方法太糟糕了？
问题陈述：
发送笑脸后，John 决定玩数组。你知道黑客喜欢玩数组吗？John 有一个从零开始的索引数组m，其中包含n非负整数。然而，他只k知道数组的第一个值，他想弄清楚其余的值。
John 知道以下内容：对于每个索引i，其中是不包含在 的先前值中k <= i < n的m[i]最小非负整数。*k*m
例如，如果k = 3和n = 4的已知值m是[2, 3, 0]，他可以算出m[3] = 1。
John 正忙于让世界变得更加开放和互联，因此，他没有时间弄清楚阵列的其余部分。帮助他是你的任务。
给定 的第一个k值m，计算该数组的第 n 个值。（即m[n - 1]）。
因为 和 的值n可能k非常大，所以我们使用伪随机数生成器来计算 的第一个k值m。给定正整数a、和b，的已知值可以计算如下：crm
m[0] = a
m[i] = (b * m[i - 1] + c) % r, 0 < i < k
输入
第一行包含一个整数 T (T <= 20)，即测试用例的数量。
接下来是 T 测试用例，每行包含 2 行。
每个测试用例的第一行包含 2 个空格分隔的整数
n,k(1 <= k <= 10^5,k < n <= 10^9)。每个测试用例的第二行包含 4 个空格分隔的整数
a,b,c,r(0 <= a, b, c <= 10^9, 1 <= r <= 10^9)。
我尝试了两种方法，但都未能在 6 分钟内返回结果，这是我的两种方法：
第一的：
import sys
cases=sys.stdin.readlines()
def func(line1,line2):
n,k=map(int,line1.split())
a,b,c,r =map(int,line2.split())
m=[None]*n #initialize the list
m[0]=a
for i in xrange(1,k): #set the first k values using the formula
m[i]= (b * m[i - 1] + c) % r
#print m
for j in range(0,n-k): #now set the value of m[k], m[k+1],.. upto m[n-1]
temp=set(m[j:k+j]) # create a set from the K values relative to current index
i=-1 #start at 0, lowest +ve integer
while True:
i+=1
if i not in temp: #if that +ve integer is not present in temp
m[k+j]=i
break
return m[-1]
for ind,case in enumerate(xrange(1,len(cases),2)):
ans=func(cases[case],cases[case+1])
print "Case #{0}: {1}".format(ind+1,ans)
第二：
import sys
cases=sys.stdin.readlines()
def func(line1,line2):
n,k=map(int,line1.split())
a,b,c,r =map(int,line2.split())
m=[None]*n #initialize
m[0]=a
for i in xrange(1,k): #same as above
m[i]= (b * m[i - 1] + c) % r
#instead of generating a set in each iteration , I used a
# dictionary this time.
#Now, if the count of an item is 0 then it
#means the item is not present in the previous K items
#and can be added as the min value
temp={}
for x in m[0:k]:
temp[x]=temp.get(x,0)+1
i=-1
while True:
i+=1
if i not in temp:
m[k]=i #set the value of m[k]
break
for j in range(1,n-k): #now set the values of m[k+1] to m[n-1]
i=-1
temp[m[j-1]] -= 1 #decrement it's value, as it is now out of K items
temp[m[k+j-1]]=temp.get(m[k+j-1],0)+1 # new item added to the current K-1 items
while True:
i+=1
if i not in temp or temp[i]==0: #if i not found in dict or it's val is 0
m[k+j]=i
break
return m[-1]
for ind,case in enumerate(xrange(1,len(cases),2)):
ans=func(cases[case],cases[case+1])
print "Case #{0}: {1}".format(ind+1,ans)
第二种方法中的最后一个 for 循环也可以写成：
for j in range(1,n-k):
i=-1
temp[m[j-1]] -= 1
if temp[m[j-1]]==0:
temp.pop(m[j-1]) #same as above but pop the key this time
temp[m[k+j-1]]=temp.get(m[k+j-1],0)+1
while True:
i+=1
if i not in temp:
m[k+j]=i
break
样本输入：
5
97 39
34 37 656 97
186 75
68 16 539 186
137 49
48 17 461 137
98 59
6 30 524 98
46 18
7 11 9 46
输出：
Case #1: 8
Case #2: 38
Case #3: 41
Case #4: 40
Case #5: 12
我已经尝试过codereview，但还没有人回复。