69. x 的平方根

Posted on | In
Words count in article: 525 | Reading time ≈ 2

题目

实现 int sqrt(int x) 函数。

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

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

示例1：

1
2
输入: 4
输出: 2

示例2：

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

解法

解法一：

使用牛顿迭代法。
牛顿迭代法（Newton’s method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。
仔细思考一下就能发现，我们需要解决的问题可以简单化理解。
从函数意义上理解：我们是要求函数f(x) = x²，使f(x) = num的近似解，即x² - num = 0的近似解。
从几何意义上理解：我们是要求抛物线g(x) = x² - num与x轴交点（g(x) = 0）最接近的点。
我们假设g(x0)=0，即x0是正解，那么我们要做的就是让近似解x不断逼近x0，这是函数导数的定义：

求导数

可以由此得到

导数

从几何图形上看，因为导数是切线，通过不断迭代，导数与x轴的交点会不断逼近x0。

导数图示

对于一般情况：

推导过程

将m=2代入：

求平方根

Java

1
2
3
4
5
6
7
int mySqrt(int x) {
    long r = x;
    while (r*r > x) {
        r = (r + x/r) / 2;
    }
    return (int) r;
}

解法二

二分查找法

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int mySqrt(int x) {  //二分法
    int low = 0;
    int up = x;
    while(low <= up){
        long mid = (low + up) / 2;
        long s = mid * mid;
        if(x == s) {
            return (int) mid;
        } else if(x > s) {
            low = mid + 1;
        } else {
            up = mid -1;
        }
    }
    return up;
}

解法三

因为最后答案肯定是个整数，那么只要找到平方数小于给定值的最大整数即可，这里要考虑到溢出问题，所以在相乘的时候，得用long。

Java

1
2
3
4
5
6
7
int mySqrt(int x) {
    for(long i = 0; ;i ++) {
        if(i * i > x) {
            return i - 1;
        }
    }
}
0%