有效的完全平方数

解题思路：

  1. 二分查找，左闭右闭区间方法；

  2. 直接去掉 num 的一半+1，因为 num>4 以上的数字的中间数平方都大于 num

复杂度：

  1. 时间复杂度：O(logn)，其中 n 为正整数 num 的最大值；

  2. 空间复杂度：O(1)；

代码实现：

function isPerfectSquare(num: number): boolean {
    let left = 1;
    // 直接去掉 num 的一半+1，因为 num>4 以上的数字的中间数平方都大于 num
    let right = (num >> 1) + 1;

    while (left <= right) {
        let mid = left + (right - left >> 1);

        if (num > mid * mid) {
            left = mid + 1;
        } else if (num < mid * mid) {
            right = mid - 1;
        } else {
            return true;
        }
    }

    return false;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 有效的完全平方数
  2. 2. 解题思路：
  3. 3. 复杂度：
  4. 4. 代码实现：