我正在研究数学+算法问题。一个regular数字定义为一个可以除以60的幂的整数-或我们可以理解，这是一个只有主除数为2、3或5的数字。
我已经解决了一个问题，但是它使用了3loops，这太慢了。
想知道如何改善我的算法。谢谢。
def regulars(n):
""" generate upto n regular num"""
ans = list ()
twos= [2** i for i in range(n)]
threes =[3** i for i in range(n)]
fives = [5** i for i in range(n)]
for twos in twos:
for three in threes:
for five in fives:
ans.append(twos*three*five)
return ans[:n]
让我们尝试通过使用此处再次考虑此问题的性质和不同的方法heapq。任何常规数字必须是上次的两倍，三倍或五倍。根据定义找到了其他一些常规数字。要利用它，我们只是进行初始化。一个以1开头的微型堆，每次x从堆中弹出一个新值，我们就产生它，然后将2x，3x，5x压入堆...直到我们达到N个整数。
但是，有些数字会重复-例如。6是2 x和3 x，是2和3的倍数，为避免发生这种情况，我们为last弹出的数字维护一个变量，并且仅当新值大于此变量时才处理新值。
然后将运行时间减少为每个推入/弹出操作的O（n logn）。
from heapq import heappush, heappop
def regulars(n):
'''generate upto n regular num'''
ans = [1] # mini-heap init value
last = 0
count = 0
while count < n: # do we have reach the threshold?
x = heappop(ans)
if x > last: # only process a new value if it's greater than last
yield x
last = x # the variable to check last num. poped
#
count += 1 # get one more, count it in
heappush(ans, 2* x)
heappush(ans, 3* x)
heappush(ans, 5* x)
if __name__ == '__main__':
n = 20
print(list(regulars(n)))
输出：＃https: //en.wikipedia.org/wiki/Regular_number（已确认匹配）
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36] # first 20
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句