LeetCode69-x的平方根

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/sqrtx/

中文链接：https://leetcode-cn.com/problems/sqrtx/

题目详述

实现 int sqrt(int x) 函数。

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

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

示例 1:

1
2
输入: 4
输出: 2

示例 2:

1
2
3
4
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

题目详解

一个非负整数 x 的平方根一定在 0~x 之间。可以运用二分查找。由于返回类型是整数，小数部分将被舍去。故最终平方根 r 必满足 r * r <= x，(r + 1) * (r + 1) > x。易知当 x <= 1，它的平方根就是它本身。

  • 二分的下限为 0。
  • 二分的上限为 x。
  • 终止条件为 r * r <= x && (r + 1) * (r + 1) > x，即 r <= x / r && (r + 1) > x / (r + 1)，使用除法防止 int 型 溢出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_00069 {

    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        int lo = 1;
        int hi = x;
        while (true) {
            int mid = lo + (hi - lo) / 2;
            if (mid > x / mid) {
                hi = mid - 1;
            } else {
                if (mid + 1 > x / (mid + 1)) {
                    return mid;
                }
                lo = mid + 1;
            }
        }
    }
}

当然，也可以换一种方式写二分。在循环条件为 lo <= hi 并且循环退出时，hi 总是比 lo 小 1，因此最后的返回值应该为 hi 而不是 lo。对于 8，退出时 hi = 2，lo = 3，。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode_00069 {

    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        int lo = 0;
        int hi = x;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int sqrt = x / mid;
            if (mid < sqrt) {
                lo = mid + 1;
            } else if (mid > sqrt) {
                hi = mid - 1;
            } else {
                return mid;
            }
        }
        return hi;
    }
}

更好的方式是使用牛顿迭代法。

  • 构造 f(x) = x * x - a。
  • 则 xn+1 = xn - f(x) / f’(x)。
  • xn+1 = ( xn + a / xn ) / 2。
1
2
3
4
5
6
7
8
9
10
public class LeetCode_00069 {

    public int mySqrt(int x) {
        long r = x;
        while (r * r > x) {
            r = (r + x / r) / 2;
        }
        return (int) r;
    }
}

实际上就是找到平方小于等于 x 的最后一个数。

1
2
3
4
5
6
7
8
9
10
11
12
public class LeetCode_00069 {

    public int mySqrt(int x) {
        int l = 1, r = x;
        while (l < r) {
            int mid = l + r + 1 >>> 1;
            if (1L * mid * mid <= x) l = mid;
            else r = mid - 1;
        }
        return r;
    }
}