2

问题

  • 给定一个正整数 n，找出总和为 n 的最小完美平方数（例如，1、4、9、16，...）。

    示例 1： 输入：n = 12 输出：3 解释：12 = 4 + 4 + 4

    示例 2： 输入：n = 13 输出：2 解释：13 = 4 + 9。

建议的解决方案 (BFS)

def numSquares(self, n):
    if n < 2:
        return n
    lst = []
    i = 1
    while i * i <= n:
        lst.append( i * i )
        i += 1
    cnt = 0
    toCheck = {n}
    while toCheck:
        cnt += 1
        temp = set()
        for x in toCheck:
            for y in lst:
                if x == y:
                    return cnt
                if x < y:
                    break
                temp.add(x-y)
        toCheck = temp

    return cnt

这个特定的 BFS 如何在 O(sqrt(n)) 中运行？因为我在想的是找到正方形需要 O(sqrt(n))。因为有2个for循环，（for y in lst1取O（sqrt（n）），for x in toCheck取O（sqrt（n）），不应该是O（n）吗？

4

1 回答 1

2

运行时间实际上是Theta(n^(3/2))。根据勒让德的三平方定理，任何整数形式4^a (8b + 7)的整数a和b都可以写成四个平方的和，但不能写成三个平方的和。让n是这种整数。有Omega(n)小于n这个数的数可以写成三个平方的和，所以在 while 循环的最后一次迭代中，toCheck有Theta(n)元素，lst有Theta(n^(1/2))。

于 2018-07-07T03:33:21.790 回答