题目
给你一个非负整数 x ,计算并返回 x 的 平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例1
输入:x = 4
输出:2
示例2
输入:x = 8
输出:2
解释:8 的平方根是 2.82842…, 由于返回类型是整数,小数部分将被舍去。
思路
这个题最显的思路就是二分法。找到平方值小于等于x的最大数字。二分法的解题关键在于:(1)需要考虑数字溢出问题(2)需要控制返回值是left还是right,这个后面从两个实现代码上进行分析
另外,牛顿迭代法是一个更有意思的思路。参考官方解法说明。牛顿法是二次收敛的,查找速度更快。涉及到很多的数学知识,都淡忘了,查了一下,收集资料于此:牛顿迭代法,常见的几种优化方法(梯度下降法、牛顿法、拟牛顿法、共轭梯度法等)、牛顿法是二次收敛的证明;另外还涉及到了导数公式、点斜式方程。
二分法代码
class Solution {
public int mySqrt(int x) {
if (x == 0 || x == 1) { // 特殊值处理
return x;
}
int left = 1, right = x; // 二分法初始两端值为1和x
// left比right小两个数值以上,保证中值既不等于left,也不等于right
// 然后left^2 < x, right^2 > x,最后返回left
while (left < right - 1) {
// 不用求和,除以2的方法,是为了避免溢出
int mid = left + (right - left) / 2;
long midPow = (long)mid * mid; // 用long避免溢出
if (midPow == x) {
return mid;
} else if (midPow < x) {
left = mid;
} else {
right = mid;
}
}
return left;
}
}
官方解法如下:
(1)用ans记录最终结果,在过程中始终记录ans^2 < x的值
(2)遍历结束条件使用l<= r,迭代进度是left=mid+1或者right=mid-1,不用考虑left^2 < x && right^2 > x
class Solution {
public int mySqrt(int x) {
int l = 0, r = x, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long) mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
}
牛顿迭代法代码
class Solution {
public int mySqrt(int x) {
if (x == 0 || x == 1) {
return x;
}
double xi = x;
while (true) {
double xj = 0.5 * (xi + x / xi);
if (Math.abs(xj - xi) < 1e-7) { //相差非常小的时候结束迭代
break;
}
xi = xj;
}
return (int) xi;
}
}
总结
数学很重要…