题目

A Hamming number is a positive integer of the form 2ⁱ3^j5^k, 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 = 2⁰3⁰5⁰
• The second smallest Hamming number is 2 = 2¹3⁰5⁰
• The third smallest Hamming number is 3 = 2⁰3¹5⁰
• The fourth smallest Hamming number is 4 = 2²3⁰5⁰
• The fifth smallest Hamming number is 5 = 2⁰3⁰5¹

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]