欢迎访问LeetCode题解合集
题目描述
实现 int sqrt(int x)
函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数,小数部分将被舍去。
题解:
法一:
二分。
有两种写法,一是 浮点数二分 ,二是 整数二分 。
浮点数二分:
直接求给定精度下x
的具体平方根,最后转换成 int
类型,这里我设置的精度为 1e-6
。
class Solution {
public:
int mySqrt(int x) {
double l = 0, r = x;
const double EPS = 1e-6;
double m;
while ( r - l > EPS ) {
m = ( l + r ) / 2.0;
if ( m * m >= x ) r = m;
else l = m;
}
return (int)r;
}
};
/*
时间:0ms,击败:100.00%
内存:5.8MB,击败:95.05%
*/
整数二分:
这种二分是找到最大的整数 k
,其满足 k^2 <= x
,因为是整数,没有精度问题。
class Solution {
public:
int mySqrt(int x) {
int l = 0, r = x, m;
while ( l < r ) {
m = (l + r + 1ll) >> 1;
if ( m <= x / m ) l = m;
else r = m - 1;
}
return r;
}
};
/*
时间:0ms,击败:100.00%
内存:5.8MB,击败:92.52%
*/
法二:
数学解法。
我们需要求得是:$x^{\frac{1}{2}}$ ,而 $x^{\frac{1}{2}} = (e^{lnx})^{\frac{1}{2}} = e^{\frac{lnx}{2}}$。
所以直接调用库函数即可得到答案。
由于指数函数和对数函数的参数和返回值均为浮点数,运算过程中会产生误差。例如当 x = 2147395600
时,$e^{\frac{lnx}{2}}$ 的计算结果与正确值 46340
相差 $10^{-11}$,这样在取整数部分时,会得到 46339
这个错误结果。所以我们可以考虑为结果补偿一个精度,比如 1e-8
,这样就可以了。
class Solution {
public:
int mySqrt(int x) {
if ( x < 2 ) return x;
int ans = exp(0.5 * log(x)) + 1e-8;
return ans;
}
};
/*
时间:0ms,击败:100.00%
内存:6MB,击败:78.76%
*/
法三:
牛顿迭代。
求 c(c>=0)
的算术平方根就是求 $f(x) = x^2 - c$ 的零点。
牛顿迭代法的本质是借助泰勒级数,从初始值开始快速向零点逼近。我们任取一个 $x_0$ 作为初始值,在每一步的迭代中,我们找到函数图像上的点 $(x_i, f(x_i))$,过该点作一条斜率为该点导数 $f’(x_i)$ 的直线,与横轴的交点记为 $x_{i+1}$。$x_{i+1}$ 相较于 $x_i$而言距离零点更近。在经过多次迭代后,我们就可以得到一个距离零点非常接近的交点。
我们选择 $x_0 = c$ 作为初始值,因为 c
的平方根是大于等于 0
的,选择初始值较小,可能会迭代到负数那个零点,而我们需要的是 正零点 。同时,迭代的停止条件可以是 $x_{i+1} - x_i <= 1e-8$ ,即两个点离的足够近。
听说这种方法比二分更快。
class Solution {
public:
int mySqrt(int x) {
if ( x < 2 ) return x;
const double EPS = 1e-8;
double c = x, x0 = x, xi;
while ( true ) {
xi = 0.5 * ( x0 + c / x0 );
if ( fabs(xi - x0) <= EPS ) break;
x0 = xi;
}
return (int)x0;
}
};
/*
时间:0ms,击败:100.00%
内存:5.8MB,击败:91.11%
*/