Python获取第n个Hamming Number代码输出结果错误问题排查

你的代码存在以下几个导致结果错误、运行异常的问题：

• 前置条件判断逻辑错误：开头的if...elif分支仅覆盖了n=1、2、3、5四个取值，其余合法n值（如n=4、n=6）都会进入else分支，这部分冗余的分支判断完全多余，反而干扰正常逻辑。
• 循环返回值计算错误：每次判断完当前i是否为汉明数后，都会执行i += 1操作，当count累加到n时，i已经多走了一步，应该返回i-1而非i。
• 递归实现的check函数有栈溢出风险：当汉明数的质因数数量过多时，递归深度会超过Python默认的递归深度上限，直接抛出异常。
• 除法存在精度风险：check函数中用/做除法，Python3中/返回浮点数，数值过大时可能出现精度丢失，导致判断错误，建议替换为整数除法//。
• 暴力枚举效率极低：逐个遍历整数判断的方案时间复杂度过高，n超过100后运行速度会大幅下降，无法满足Codewars的时间限制要求。

基础修复版（保留暴力枚举逻辑，仅修复正确性问题） #

def hamming(n):
    count = 0
    i = 1
    while count < n:
        if check(i):
            count += 1
        if count == n:
            return i
        i += 1

def check(n):
    while n % 2 == 0:
        n = n // 2
    while n % 3 == 0:
        n = n // 3
    while n % 5 == 0:
        n = n // 5
    return n == 1

高效优化版（三指针动态规划，适合大n场景） #

def hamming(n):
    ham = [1] * n
    i2 = i3 = i5 = 0
    for idx in range(1, n):
        next2, next3, next5 = ham[i2] * 2, ham[i3] * 3, ham[i5] * 5
        ham[idx] = min(next2, next3, next5)
        if ham[idx] == next2:
            i2 += 1
        if ham[idx] == next3:
            i3 += 1
        if ham[idx] == next5:
            i5 += 1
    return ham[-1]

内容的提问来源于stack exchange，提问作者Samarth Goyal