SlovinG
Search K

Appearance

367.有效的完全平方数 ​

难度：简单

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

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

提示：

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

解题思路 ​

求 num 开方后是不是一个整数，显然平方根一定是 1，2，3 ... num 中的一个数。

从一个 有序的、无重复的 序列中寻找目标值，很适合使用二分查找法。

综合 69 题的经验和题干中所说明的数据范围，为了避免 数据溢出 的问题，也为了节省内存。我们这里不采用 middle * middle == num 的判断方式，而是采用 num / middle == middle 的判断方式，但要注意使用 整数除法 时会面临的 数值截断 问题：

例如 10 / 3 == 3 成立，但是 3 * 3 = 9，显然仅凭 num / middle == middle 的判断方式，在某些情况下是会得到错误结果的。

那如果用 double 除法呢？

其实 double 除法也会面临数据截断的问题，只是精度在一定程度上相对整数除法提高了而已。

换个思路，在整数除法中，采用 num / middle == middle && middle * middle == num 的方式可以吗？

看起来确实可以验证出正确的结果，但是这样会不会又出现数据溢出的问题呢，毕竟 middle * middle == num 是我们一开始就抛弃的方案。

答案是不会，因为哪怕 num = Integer.MAX_VALUE，也只有当 num * 1.0 / x = x.小数部分 的时候才会触发 && 后面的部分，而在这种情况下，x * x 的结果显然是小于 num 的，也就是不会超过 int 的存储范围，也就不会导致数据溢出了。

同时要注意，当 num * 1.0 / x = x.小数部分 && x * x != num 成立的时候，显然也存在 (x - 1) * (x - 1) < num 和 (x + 1) * (x + 1) > num，这说明 num 不是一个完全平方数。

我的过程 ​

  1. 先取中点 middle，然后判断 num / middle == middle 是否成立

  2. num / middle == middle 的时候，判断 middle * middle == num 是否成立

  3. 若 middle * middle == num 成立，则 middle 刚好是目标值，返回 true

  4. 若 middle * middle == num 不成立，根据上面的分析，目标值不存在，返回 false

  5. num / middle < middle 的时候，则从 middle 左边继续寻找

  6. num / middle > middle 的时候，则从 middle 右边继续寻找

  7. 当 right > left 的时候退出循环，此时目标值不存在，返回 false

我的代码 ​

java
public boolean isPerfectSquare(int num) {
    int left = 1;
    int right = num;
    return binarySearch(left, right, num);
}

public boolean binarySearch(int left, int right, int target) {
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (target / middle == middle) {
            //简化逻辑的写法
            return (middle * middle == target);
        } else if (target / middle < middle) {
            right = middle - 1;
        } else if (target / middle > middle) {
            left = middle + 1;
        }
    }
    return false;
}

时间复杂度：O(log n)

空间复杂度：O(1)

总结 ​

当思路想清楚的时候，代码的编写不过是几分钟的事情。

各种边缘条件、临界情况和极端数例的存在，在思考算法的时候都要考虑到。