且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

[LeetCode] Sqrt(x) 求平方根

更新时间:2022-08-14 17:35:08

Implement int sqrt(int x).

Compute and return the square root of x.

这道题要求我们求平方根,我们能想到的方法就是算一个候选值的平方,然后和x比较大小,为了缩短查找时间,我们采用二分搜索法来找平方根,由于求平方的结果会很大,可能会超过int的取值范围,所以我们都用long long来定义变量,这样就不会越界,代码如下:

解法一

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

这道题还有另一种解法,是利用牛顿迭代法,记得高数中好像讲到过这个方法,是用逼近法求方程根的神器,在这里也可以借用一下,可参见网友Annie Kim's Blog的博客,因为要求x2 = n的解,令f(x)=x2-n,相当于求解f(x)=0的解,可以求出递推式如下:

xi+1=xi - (xi- n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2

解法二

// Newton's method
class Solution {
public:
    int sqrt(int x) {
        if (x == 0) return 0;
        double res = 1, pre = 0;
        while (res != pre) {
            pre = res;
            res = (res + x / res) / 2;
        }
        return int(res);
    }
};

本文转自博客园Grandyang的博客,原文链接:求平方根[LeetCode] Sqrt(x) ,如需转载请自行联系原博主。