python - 如何获得重复小数的长度？

Question

我面试了，问题是如何获取重复小数的长度？

例如

1/3=0.3333..., it returns 1,
5/7=0.7142857142857143, it returns 6, since 714285 is the repeating decimal.
1/15=0.066666666666666, it returns 1.
17/150=0.11333333333333333, it returns 1. since 3 is the repeating decimal.

我试着写了一段代码

def solution(a, b):
    n = a % b
    if n == 0:
        return 0

    mem = []
    n *= 10

    while True:
        n = n % b
        if n == 0:
            return 0
        if n in mem:
            i = mem.index(n)
            return len(mem[i:])
        else:
            mem.append(n)
        n *= 10

但是，我的代码无法通过所有测试。它的时间复杂度是 O(n*logn)。我该如何改进它并使其时间复杂度为 O(n)？

Answer 1

可能正确的方法是遵循@Henry 建议的数学堆栈交换链接。但关于您的代码，这是我的优化版本。这里的关键点是使用字典而不是数组 - 在这种情况下 in 操作要快得多。

def solution(a, b):
    n = a % b
    if n == 0:
        return 0

    mem = {}
    n *= 10
    pos = 0

    while True:
        pos += 1
        n = n % b
        if n == 0:
            return 0
        if n in mem:
            i = mem[n]
            return pos - i
        else:
            mem[n] = pos
        n *= 10

在我的 29/39916801 计算机上，此代码在几秒钟内完成计算。