解法1：一个个遍历
java代码：
class Solution {
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
if (x == 1) {
return 1;
}
for (int i = 1; i < x ; i++) {
if (i * i <= x && (long)(i + 1) * (i + 1) > (long) x) {
return i;
}
}
return 0;
}
}
复杂度
- 时间复杂度：
O(n)，其中 n 是x大小。 - 空间复杂度：
O(1)
解法2：二分查找
java代码
class Solution {
public int mySqrt(int x) {
int l = 0, r = x, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if ((long) mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
}
复杂度
- 时间复杂度：
O(logn)，其中 n 是x大小。 - 空间复杂度：
O(1)
解法3：数学转化
经过数学换算，x的平方根可转换成e*(1/2 * lnx)
注意： 由于计算机无法存储浮点数的精确值,而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。因此在得到结果的整数部分 ans 后，我们应当找出 ans 与 ans+1 中哪一个是真正的答案。
class Solution {
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
int ans = (int) Math.exp(0.5 * Math.log(x));
return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
}
}
复杂度
- 时间复杂度：
O(1) - 空间复杂度：
O(1)