题目
A Hamming number is a positive integer of the form 2i3j5k, for some non-negative integers i, j, and k.
Write a function that computes the nth smallest Hamming number.
Specifically:
- The first smallest Hamming number is 1 = 203050
- The second smallest Hamming number is 2 = 213050
- The third smallest Hamming number is 3 = 203150
- The fourth smallest Hamming number is 4 = 223050
- The fifth smallest Hamming number is 5 = 203051
The 20 smallest Hamming numbers are given in example test fixture.
Your code should be able to compute all of the smallest 5,000 (Clojure: 2000) Hamming numbers without timing out.
我的答案
def hamming(num):
lst = [1]
a, b, c = 2, 3, 5
l, m, n = 0, 0, 0
for i in range(1, num):
lst.append(min(a, b, c))
if lst[-1] == a:
l += 1
a = 2 * lst[l]
if lst[-1] == b:
m += 1
b = 3 * lst[m]
if lst[-1] == c:
n += 1
c = 5 * lst[n]
return lst[-1]
其他精彩答案
def hamming(n):
bases = [2, 3, 5]
expos = [0, 0, 0]
hamms = [1]
for _ in range(1, n):
next_hamms = [bases[i] * hamms[expos[i]] for i in range(3)]
next_hamm = min(next_hamms)
hamms.append(next_hamm)
for i in range(3):
expos[i] += int(next_hamms[i] == next_hamm)
return hamms[-1]
