SlovinG
Search K

Appearance

69.x的平方根 ​

难度：简单

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

  • 0 <= x <= 2^(31) - 1

解题思路 ​

求 x 的平方根的整数部分，所以平方根一定是 1，2，3 ... x 中的一个数。

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

我的思路：

  1. 先取中点 middle，然后判断 middle * middle 是否等于 x

  2. middle * middle = x 的时候，middle 就是目标值，直接返回

  3. middle * middle < x 的时候，则从 middle 右边继续寻找；

    注意在这一步中，要往 result 中暂存一下 middle 的值，因为题干中说 “8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去”；

    则当 2 * 2 = 4 < 8 的时候，2 其实已经是目标值了，如果抛弃 2，那么由于 3 * 3 = 9 > 8，此时目标值就找不到了，所以需要暂存 middle

  4. middle * middle > x 的时候，则从 middle 左边继续寻找

    在这一步中如果延续第 3 步的思路，那么是不是应该往 result 中暂存 middle - 1 的值呢？

    答案是：可以，但没必要。

    因为在我们的代码中，只要目标值存在，那么在 倒数第二次循环 的时候，肯定会进入 middle * middle == x 或者 middle * middle < x，此时就已经保存了 middle 的值，所以没必要在 最后一次循环 的时候，也就是触发 middle * middle > x 的时候再保存一次了。

    综上，第 3 步和第 4 步暂存 result 的操作，只需要保留任何一个就可以满足我们的需求。

  5. 当 right > left 的时候退出循环，此时 result 里存的就是目标值

我的代码 ​

java
public int mySqrt(int x) {
    int left = 1;
    int right = x;
    return binarySearch(left, right, x);
}

public int binarySearch(int left, int right, int x) {
    int result = 0;
    while (left <= right) {
        long middle = left + (right - left) / 2;
        if (middle * middle == x) {
            result = (int) middle;
            break;
        } else if (middle * middle < x) {
            result = (int) middle;
            left = (int) (middle + 1);
        } else if (middle * middle > x) {
            // result = (int) middle - 1;
            right = (int) (middle - 1);
        }
    }
    return result;
}

时间复杂度：O(log n)

空间复杂度：O(1)

避坑 ​

注意，题目中写到输入值的规模为：0 <= x <= 2^(31) - 1。

而在 Java 中 int 的存储范围为：-2^(31) ~ 2^(31) - 1， long 的存储范围为：-2^(63) ~ 2^(63) - 1

那么上述代码中，如果不使用 long 型变量来声明 middle，那么当 x 的值过大的时候（例如 x = Integer.MAX_VALUE 时），尽管 middle 不会超过 int 的存储范围，但在 middle * middle 的时候，还是会发生 数值溢出，运算的结果将会被截断，只保留低 32 位的值，那么此时的 middle * middle 将不会是我们期望的值。

事实上，我们这里写 middle = left + (right - left) / 2，已经是在防止数据溢出了，当然它的运算结果和 (left + right)/2 是相同的。

更优雅的写法 ​

java
public int mySqrt(int x) {
    int left = 1;
    int right = x;
    return binarySearch(left, right, x);
}

public int binarySearch(int left, int right, int target) {
    int result = 0;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (target / middle == middle) {
            result = middle;
            break;
        } else if (target / middle > middle) {
            result = middle;
            left = middle + 1;
        } else if (target / middle < middle) {
            right = middle - 1;
        }
    }
    return result;
}

上述写法中，使用 target / middle == middle 这样的除法来规避了 middle * middle 可能会引发的数值溢出的问题。

总结 ​

题干中对数据大小的提示，需要多留意。