题目链接

题目描述

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。

示例

示例1：

输入：num = 16 输出：true

提示

  • 1 <= num <= 2^31 - 1

    思路

    思路1：二分查找

    常规的题目。

    思路2：牛顿法

    详细请看0069-x的平方根

    题解

    思路1：二分查找

    1. class Solution {
    2.  public:
    3.   bool isPerfectSquare(int num) {
    4.       if (num < 2) {
    5.           return true;
    6.       }
    7.       int left = 0, right = num / 2;
    8.       while (left <= right) {
    9.           int mid = ((right - left) >> 1) + left;
    10.           long long square = (long long)mid * mid;
    11.           if (square == num) {
    12.               return true;
    13.           } else if (square > num) {
    14.               right = mid - 1;
    15.           } else {
    16.               left = mid + 1;
    17.           }
    18.       }
    19.       return false;
    20.   }
    21. };

    思路2：牛顿法

    class Solution {
 public:
  bool isPerfectSquare(int num) {
      if (num < 2) {
          return true;
      }

      long i = num;
      while (i * i > num) {
          i = (i + num / i) / 2;
      }

      return i * i == num;
  }
};

    复杂度分析

    思路1：二分查找

  • 时间复杂度：0367-有效的完全平方数 - 图1

  • 空间复杂度：0367-有效的完全平方数 - 图2

    思路2：牛顿法

  • 时间复杂度：0367-有效的完全平方数 - 图3

  • 空间复杂度：0367-有效的完全平方数 - 图4