Leetcode--69

Leetcode–69

X的平方根

给你一个非负整数$x$ ，计算并返回 $x$的算术平方根 。
由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去 。
注意：不允许使用任何内置指数函数和算符，例如 $pow(x,0.5)$ 或者 x ∗ ∗ 0.5 x^{**}0.5 x∗∗0.5 。

示例 1：
输入：x = 4
输出：2

示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

提示：
0 ≤ x ≤ 2 31 − 1 0 \leq x \leq 2^{31} - 1 0≤x≤231−1

思路

方法一：袖珍计算器算法

通过换指数的底来求。
x = x 1 / 2 = ( e l n x ) 1 / 2 = e 1 / 2 l n x \sqrt x=x^{1/2}=(e^{lnx})^{1/2}=e^{1/2lnx} x ​=x1/2=(elnx)1/2=e1/2lnx
注意：由于计算机无法存储浮点数的精确值（浮点数的存储方法可以参考 IEEE 754，这里不再赘述），而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。例如当 $x=2147395600$时， e 1 / 2 l n x e^{1/2lnx} e1/2lnx 的计算结果与正确值 $46340$相差 1 0 − 11 10^{-11} 10−11，这样在对结果取整数部分时，会得到$46339$这个错误的结果。
因此，在得到结果的整数部分$ans$后，我们要判断判断$ans+1$与$ans$哪个是真正的答案。
具体的代码如下（C++实现）

class Solution {
public:int mySqrt(int x) {if(x==0){return 0;}int ans = exp(0.5*log(x)); return ((long long)(ans + 1)*(ans+1)<=x?ans+1:ans);}
};

方法二：二分法

$x$的平方根的整数部分$ans$是满足 k 2 ≤ x k^2 \leq x k2≤x的最大$k$值，我们对整数$k$进行二分查找，得到答案$ans$。在这里我们将下界设为$0$，将上界粗略地设为$x$，通过比较$mid$和$x$的大小关系，来更新上界和下界，最后得到答案$ans$。
相较于传统的二分法，该问题需要引入一个变量$ans$，来记录最后的答案，而这个值的更新时刻是该问题的关键。
注意到，$ans$一定满足$ans\ast ans\le x$，故只有当$mid\ast mid\le x$时，将$mid$的值赋予$ans$，而更新上界和下界的步骤和传统的二分法类似。
由此，具体的代码如下（C++实现）

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

方法三：牛顿迭代法

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！