0%

面试题-求非负数平方根

发表于 分类于 阅读次数： Valine：

题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sqrtx

解法

二分法

  1. 定义左边界0，右边界x；取左右边界的中位数。
  2. 计算中位数的平方，判断与x之间的大小；小于x则收缩左边界，大于x则收缩右边界，如此循环
  3. 等右边界贴近左边界（甚至<）时，左边界则是最优解
1
2
3
4
5
6
7
8
9
10
PS：取出中位数时一定要+1

    否则会存在这种情况，进退两难进入死循环 如：
    中位数：46339 left:46339 right:46340

    而+1之后 如：
    中位数：46339 left:46337 right:46340
    中位数：46340 left:46339 right:46340

    此时left：46339就是最优解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static long mySqrt(int x) {
    // 要把搜索的范围设置成长整型, 测试用例 2147395599 会超出int的最大长度

    // 比较特殊的是 0 和 1，因此左边界设置0，有边界设置 x/2 + 1（一个非负数n，它的平方根不会大于（n/2+1））

    long left = 0;
    long right = x / 2 + 1;
    // 将在左右区间内寻找
    while (left < right) {
        // 计算左右边界的中位数
        long mid = (left + right + 1) / 2;
        System.out.println("中位数：" + mid + " （left:" + left + " right:" + right + "）");
        // 中位数平方，判断是否接近
        long square = mid * mid;
        if (square > x) {
            // 结果>x，右边界收缩到中位数，但是中位数明显不是， -1 ，准备下次循环重新计算
            right = mid - 1;
        } else {
            // 结果<=x，左边界等于 中位数
            left = mid;
        }
    }
    // 此时左边界已经<=x，且右边界贴近（甚至<）左边界极限，说明左边界已经是最近似值
    return (int) left;
}