降低时间复杂度以找到平方整数

Question

下面的函数是搜索范围a和b之间的平方整数。但问题是它超过了时间限制。范围可能是 1<=a<=b<=10^9.

function squares(a, b) {
    let count = 0;
    while(a<=b)
    {
        if(Number.isInteger(Math.sqrt(a)))
        {
            count++;
        }
        a++;
    }
    return count;
}

谁能帮我降低这个的复杂性？

Answer 1

您可以尝试“创建”它们，而不是检查数字是否是完全平方数。

One idea you could have is to find one, then generate the next one, as (n+1)^2-n^2=2n+1. This would be pretty efficient, but we could do a lot better.

既然只需要计算平方数，我们就可以简单地计算a和b的平方根。并计算这些平方根之间的整数个数（只需从另一个中减去一个）。但是当a和b其中之一本身是正方形时要小心。

因此，我们可以这样写：

function squares(a, b) {
    const sqrtA = Math.sqrt(a)
    const floorA = Math.floor(sqrtA)
    const sqrtB = Math.sqrt(b)
    const ceilB = Math.floor(sqrtB)
    
    let n = ceilB -  floorA
    
    if (floorA == sqrtA) { // A is a square
        n += 1
    }
    
    return n
}

降低时间复杂度以找到平方整数

Reducing time complexity to find square Integers

javascript

math

time-complexity