美文网首页
LeetCode 69.x的平方根

LeetCode 69.x的平方根

作者: 饼干不干 | 来源:发表于2019-05-16 18:55 被阅读0次

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

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

C

牛顿迭代法

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

C++

二分法,令left = 0, right为int最大值,mid为left和right的中间值。始终保持要求的值在left和right之间。
进入循环——如果mid的平方小于等于x并且mid+1的平方大于等于x则返回mid
否则:如果mid的平方小于x,说明答案在mid的右边,left = mid + 1,mid的平方大于x,说明答案在mid的左边,right = mid – 1
注意:令left、right、mid都是long型因为为了避免mid*mid的结果超出整型范围

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

相关文章

网友评论

      本文标题:LeetCode 69.x的平方根

      本文链接:https://www.haomeiwen.com/subject/lmdwaqtx.html