题目描述

题目描述

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true

示例 2：

输入：num = 14
输出：false

提示：

1 <= num <= 231 - 1

思路

暴力循环

从 1 开始，算平方到 num，如果有则 true，否则 false

  1. public boolean isPerfectSquare(int num) {
  2.     for (int i = 0; i < num; i++) {
  3.         if (Math.pow(i, 2) == num) {
  4.             return true;
  5.         }
  6.     }
  7.     return false;
  8. }

很自然，超时了

二分查找

image.png
367. 有效的完全平方数 - 图2

  1. public boolean isPerfectSquare(int num) {
  2.     if (num < 2) {
  3.         return true;
  4.     }
  6.     long left = 2, right = num / 2, x, guessSquared;
  7.     while (left <= right) {
  8.         x = left + (right - left) / 2;
  9.         guessSquared = x * x;
  10.         if (guessSquared == num) {
  11.             return true;
  12.         }
  13.         if (guessSquared > num) {
  14.             right = x - 1;
  15.         } else {
  16.             left = x + 1;
  17.         }
  18.     }
  19.     return false;
  20. }
  • 时间复杂度：O(logN)
  • 空间复杂度：O(1)

牛顿迭代法（大概理解）

image.png
image.png

  1. public boolean isPerfectSquare(int num) {
  2.     if (num < 2) return true;
  4.     long x = num / 2;
  5.     while (x * x > num) {
  6.         x = (x + num / x) / 2;
  7.     }
  8.     return (x * x == num);
  9. }
  • 时间复杂度：O(logN)
  • 空间复杂度：O(1)

哔哔一下

牛顿迭代。。第一次听，长见识了