欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

九章算法 | Facebook面试题:对x开根 II

程序员文章站 2022-03-08 08:10:01
...

实现 double sqrt(double x) 并且 x >= 0

计算并返回x开根后的值。

在线评测地址:LintCode 领扣

例1:

输入: n = 2 
输出: 1.41421356

例2:

输入: n = 3
输出: 1.73205081

【题解】

算法:二分

此题有两种做法,一种是牛顿迭代法,一种是二分,这里介绍二分法

  • 二分浮点数与寻常二分不同的是while中变成了whlie(left+eps<right)
  • 注意小数情况,若x<1将右边界扩大到1可避免结果错误(比如0.04=0.2*0.2)如果我们不将x右边界扩大到1,则无法在[0,0.04]的区间范围内找到正解

复杂度分析

  • 时间复杂度O(log(x))

  • 二分的复杂度

  • 空间复杂度O(1)

  • 无需额外空间

public class Solution {
    /**
     * @param x: a double
     * @return: the square root of x
     */
    public double sqrt(double x) {
        double left = 0,right = x,mid;
        if (right < 1) {
            right = 1;
        }
        while (left + 1e-12 < right) {
            mid = left + (right - left) / 2;
            if (mid * mid < x) {
                left = mid;
            }
            else{
                right = mid;
            }
        }
        return left;
    }
}

更多题解参见:九章算法