- 给你一个非负整数 x，计算并返回x的算术平方根
- 由于返回类型是整数，结果只保留 整数部分，小数部分将被舍去
- 不允许使用任何内置指数函数和算符，如
pow(x,0.5)
方法一：暴力破解
从
i
=
0
i=0
i=0 开始遍历，直到满足
i
2
≤
x
<
(
i
+
1
)
2
i^2 \leq x < {(i+1)}^2
i2≤x<(i+1)2 时，
i
i
i 即是
x
x
x 的算术平方根。
代码实现
int mySqrt(int x) {
int nRes = 0;
int a = nRes * nRes;
int b = 0;
while (a <= x) {
if (a < INT_MAX - 2 * nRes - 1) {
b = (nRes + 1) * (nRes + 1);
}
else {
break;
}
if (a <= x && b > x) {
break;
}
nRes++;
}
return nRes;
}
时间复杂度：
O
(
x
)
O(x)
O(x)
空间复杂度：
O
(
1
)
O(1)
O(1)
利用公式：
x
=
x
1
/
2
=
(
e
ln
?
x
)
1
/
2
=
e
1
2
ln
?
x
\sqrt{x} = x^{1/2} = {(e^{\ln{x}})}^{1/2} = e^{\frac{1}{2}\ln{x}}
x
?=x1/2=(elnx)1/2=e21?lnx
由于计算机无法存储浮点数的精确值，而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。因此在得到结果的整数部分
a
n
s
ans
ans 后，还要验证
a
n
s
ans
ans 和
a
n
s
+
1
ans+1
ans+1 哪个是正确的答案。
代码实现
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);
}
};
时间复杂度：
O
(
1
)
O(1)
O(1)
空间复杂度：
O
(
1
)
O(1)
O(1)
在方法一的基础上进行优化，方法一的遍历范围 [0,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 long)mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
};
时间复杂度：
O
(
log
?
x
)
O(\log{x})
O(logx)
空间复杂度：
O
(
1
)
O(1)
O(1)
|