2019-12-02 x 的平方根

转发 https://blog.csdn.net/qq_41231926/article/details/82861877

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2

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

思路一：从1开始逐个查找

思路一是最先能想到的简单粗暴的解法。从数字1开始找，一旦找到平方值等于x的数字i，直接返回i。如果找到平方值大于x的数字i，需要返回i - 1。

需要注意的是，为了防止做乘法运算时越界，需要强转为long类型。

时间复杂度是O(sqrt(x))。空间复杂度是O(1)。

JAVA代码：

public class Solution {
    
    public int mySqrt(int x) {
        for (long i = 1; i <= x; i++) {
            if(i * i > x) {
                return (int)(i - 1);
            }else if(i * i == x) {
                return (int)i;
            }
        }
        return 0;
    }
}

思路二：二分查找法

思路一的时间复杂度太高，可以用二分法进行改进。

运算过程中涉及到乘法运算时同样需要强转为long类型防止越界。

时间复杂度是O(logx)。空间复杂度是O(1)。

JAVA代码：

public class Solution {
 
    public int mySqrt(int x) {
        int left = 0, right = x / 2 + 1;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (mid * mid == x) {
                return (int) mid;
            } else if (mid * mid < x) {
                left = (int) (mid + 1);
            } else {
                right = (int) (mid - 1);
            }
        }
        return right;
    }
 
}

思路三：牛顿法求解平方根

求一个数n的平方根，相当于求解方程f(x) = x ^ 2 - n的解。

牛顿法

牛顿法的过程如下：

假设某个迭代点的值是Xi，我们求其下一个迭代点的值Xi+1。如上图所示，在（Xi, Yi）点，我们做函数f(x)的切线，其与横轴相交的点就是下一个迭代点Xi+1。

根据直线的方程我们很容易写出关系式：f(Xi) = f(Xi)' * (Xi - Xi+1)。由该式可以推得：Xi+1 = (n + Xi ^ 2) / (2 * Xi)。

那么，循环结束的条件是什么呢？

显然是Xi与Xi+1十分接近时，就可以终止上述迭代过程了。

牛顿法求解的时间复杂度与初值点的选取有关，如果初值点的选取离真实解十分接近，那么迭代速度就更快。如果初值点的选取十分离谱，甚至可能会发散，不收敛。空间复杂度是O(1)。

JAVA代码：

public class Solution {
 
    public int mySqrt(int x) {
        double pre = 0, cur = 1;
        while (Math.abs(pre - cur) >= 0.000001) {
            pre = cur;
            cur = (x + cur * cur) / (2 * cur);
        }
        return (int) pre;
    }
 
}