题目描述:
实现 int sqrt(int x)函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1：
输入: 4
输出: 2
示例 2：
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,由于返回类型是整数，小数部分将被舍去。
题目分析:
一眼看到这道题，第一种方法，我们肯定会想到直接调用数学函数求解，笔试面试这样写想必你已经凉凉了。
第二种方法，我们也可以使用暴力破解法求解，首先，如果x为0或1，则它们的非负平方根是它们本身。我们可以大致取中点值，从1到中点值进行遍历，如果当前数平方小于等于x且下一位数平方大于x，则当前数为平方根，但暴力解法耗时长。
第三种方法，二分查找，首先定义左右边界，左边界为0，右边界为x，当左边界小于等于右边界执行循环，求出这段区间的中点值，用中点值的平方与x进行比较，如果中点值平方大于x，则说明答案应该在左子区间，我们对区间范围进行缩小，更新右边界为中点值左边元素。如果中点值平方小于x，则说明答案应该在右子区间，我们对区间范围进行缩小，更新左边界为中点右边元素。如果中点值平方刚好等于x，在说明中点值就是我们要求的答案。如果在循环遍历过程中，左边界大于右边界且左边界平方大于x而右边界平方小于x，即右边界值比左边界值小，返回右边界值即可。
第四种方法，牛顿迭代法，我们可以把这道题转化为函数求解问题。依题意，我们可以将求解平方根转换为求解函数
f
(
y
)
=
y
2
−
x
=
0
f(y) = y^{2} - x = 0
f(y)=y2−x=0的解。根据牛顿迭代法公式
x
n
+
1
=
x
n
−
f
(
x
n
)
f
′
(
x
n
)
x_{n+1} = x_{n} − \frac{f(x_{n})}{f′(x_{n})}
xn+1=xn−f′(xn)f(xn)。因为
f
(
y
)
=
y
2
−
x
=
0
f(y) = y^{2} − x = 0
f(y)=y2−x=0，我们把函数代入迭代公式得到
y
n
+
1
=
y
n
+
x
y
n
2
y_{n+1} = \frac{y_{n} + \frac{x}{y_{n}}}{2}
yn+1=2yn+ynx，再按牛顿迭代法求解即可。
题解一(笔试面试必挂解):
执行用时: 1 ms
内存消耗: 35.2 MB
class Solution {
public int mySqrt(int x) {
// 笔试面试必挂解法，直接调用库函数
return (int) Math.sqrt(x);
}
}
题解二(暴力解法):
执行用时: 52 ms
内存消耗: 35.2 MB
class Solution {
public int mySqrt(int x) {
// 0的平方根为0，1的非负平方根为1
if (x == 0 || x == 1)
return x;
// 取中点值
long mid = x / 2;
// 从1开始遍历
for (long i = 1; i <= mid; ++i) {
// 如果当前数平方小于等于x且下一位数平方大于x
if (i * i <= x && (i + 1) * (i + 1) > x)
// 则当前数为平方根
return (int)i;
}
// 方法一定要返回一个int值
return -1;
}
}
题解三(二分查找法):
执行用时: 2 ms
内存消耗: 35.5 MB
class Solution {
public int mySqrt(int x) {
// 定义左右边界
long left = 0, right = x;
// 当左边界小于等于右边界执行循环
while(left <= right) {
// 定义中点
long mid = (left + right) / 2;
// 中点值平方大于x，缩小范围至左区间
if(mid * mid > x)
// 右边界更新为中点的左边元素
right = mid - 1;
// 中点值平方小于x，缩小范围至右区间
else if(mid * mid < x)
// 左边界更新为中点的右边元素
left = mid + 1;
// 中点值平方等于x，即mid为x的平方根
else if(mid * mid == x)
// 返回平方根整数部分
return (int) mid;
}
// 如果左边界平方大于x而右边界平方小于x，即右边界值符合条件
if(left * left > x && right * right < x)
// 返回右边界值
return (int) right;
return -1;
}
}
题解四(牛顿迭代法):
执行用时: 2 ms
内存消耗: 35.5 MB
class Solution {
public int mySqrt(int x) {
long a = x;
while (a * a > x)
a = (a + x / a) / 2;
return (int) a;
}
}
题目来源:力扣(LeetCode)