69、x 的平方根

leetcode

Created At : 2020-07-26 00:19

Count:665 Views 👀 :

Comment:

69、x的平方根
1. 示例 1:
2. 示例 2:

题解

1、二分查找
2、牛顿迭代法
3、袖珍计算器法

69、x的平方根

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2

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

链接：https://leetcode-cn.com/problems/sqrtx

题解

1、二分查找

题目的本质就是以最快的速度找到：平方小于等于x的最大的正整数

public class Solution {

    int mySqrt(int x) {
        if (x <= 1) {return x;}
        int res = -1;
        int l = 0;
        int r = x;
        while (l <= r) {
            int mid = l + (r - l)/2;
            if ((long)mid*mid <= x){
                res = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return res;
    }
}

2、牛顿迭代法

牛顿迭代法是一种可以用来快速求解函数零点的方法

不妨构造以下的函数：

y = f(x) = x^{2} - C , f’(x) = 2x
$$

其中：C去题目中的$x_0$

牛顿迭代法步骤：

从x = x_0 求切线方程:$y_l = f’(x_i)(x - x0) + y_0 = 2x_i(x-x_i) - x_i^2 - C = 2x_ix - (x_i^2 +C)$
计算切线与横轴的交点，获得横坐标 x’: $x_{i+1} = \frac{1}{2}(x_i+\frac{C}{x_i})$
更新x = x’,重复前两步，直到x与 x’的距离小于$1e-7$

class Solution {
    public int mySort(int x) {
        if (x <= 0) {
            return x;
        }

        double C = x,x0 = x;
        while(true) {
            // 计算x0处切线与横轴相交的横坐标
            double xi = 0.5 *(x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            // 更新的切点
            x0 = xi;
        }
        return (int) x0;
    }
}

3、袖珍计算器法

数学公式：
$$ \sqrt{x} = x^{\frac{1}{2}} = (e^{\ln(x)})^{\frac{1}{2}}=e^{\frac{\ln x}{2}}$$

注意：由于计算机无法存储浮点数的精确值（浮点数的存储方法可以参考 IEEE 754，这里不再赘述），而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。例如当 x = 2147395600x=2147395600 时，$e^{\frac{1}{2} \ln x}$ 的计算结果与正确值 4634046340 相差 $10^{-11}$ ，这样在对结果取整数部分时，会得到 4633946339 这个错误的结果。

因此在得到结果的整数部分 $\textit{ans}$ 后，我们应当找出 $\textit{ans}$ 与 $\textit{ans} + 1$ 中哪一个是真正的答案。

class Solution{
    public int mySort(int x) {
        if (x <= 1) {
            return x;
        }
        int ans = (int)Math.exp(0.5*Math.log(x));
        // 判断anx+1是否满足要求
        return (long) (ans + 1)*（ans + 1) <= x ? ans + 1 : ans;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com