有效的完全平方数

发表于 | 分类于 |
字数统计: 215 字 | 阅读时长 ≈ 1 分钟

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

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

示例 1：
输入：num = 16
输出：true

示例 2：
输入：num = 14
输出：false

方法一：二分查找法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isPerfectSquare(int num) {
        int i = 1, j = num / 2 + 1;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (num / mid == mid) {
                if(num % mid==0) {
                    return true;
                }
                return false;
            } else if(num / mid < mid) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return false;
    }
}

复杂度分析

  • 时间复杂度：O(logN)。
  • 空间复杂度：O(1)。

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗：35.2 MB, 在所有 Java 提交中击败了53.97%的用户