class Solution {
public:
int mySqrt(int x) {
}
};
69. x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1原站题解
java 解法, 执行用时: 1 ms, 内存消耗: 38.6 MB, 提交时间: 2023-11-28 10:10:37
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;
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 6.2 MB, 提交时间: 2023-11-28 10:10:23
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;
}
};
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.1 MB, 提交时间: 2023-11-28 10:10:05
class Solution {
public:
int mySqrt(int x) {
if (x == 0) {
return 0;
}
double C = x, x0 = x;
while (true) {
double xi = 0.5 * (x0 + C / x0);
if (fabs(x0 - xi) < 1e-7) {
break;
}
x0 = xi;
}
return int(x0);
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 39 MB, 提交时间: 2023-11-28 10:09:45
class Solution {
public int mySqrt(int x) {
if ( x == 0 ) return 0;
// 牛顿迭代
double x0 = x, C = x;
while ( true ) {
double xi = 0.5 * ( x0 + C / x0 );
if ( Math.abs(xi-x0) < 1e-7 ) {
break;
}
x0 = xi;
}
return (int) x0;
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2020-11-11 15:30:03
func mySqrt(x int) int {
if x == 0 {
return 0
}
x0, C := float64(x), float64(x)
for {
xi := 0.5 * ( x0 + C / x0)
if math.Abs(x0-xi) < 1e-7 {
break
}
x0 = xi
}
return int(x0)
}
python3 解法, 执行用时: 36 ms, 内存消耗: 13.5 MB, 提交时间: 2020-11-11 15:27:21
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0: return 0
# 牛顿迭代
x0, C = float(x), float(x)
while True:
xi = 0.5 * ( x0 + C / x0 )
if abs(xi-x0) < 1e-7:
break
x0 = xi
return int(x0)
golang 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2020-11-11 15:10:19
func mySqrt(x int) int {
left, right, ans := 0, x, 0
for left <= right {
mid := (left+right) / 2
if mid * mid <= x {
ans = mid
left = mid + 1
} else {
right = mid - 1
}
}
return ans
}
python3 解法, 执行用时: 48 ms, 内存消耗: 13.5 MB, 提交时间: 2020-11-11 15:07:43
class Solution:
def mySqrt(self, x: int) -> int:
# 二分查找法
left, right, ans = 0, x, -1
while left <= right:
mid = ( left + right )//2 # 取中间数, 整
if mid**2 <= x:
ans = mid
left = mid+1
else:
right = mid-1
return ans
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2020-11-11 14:48:23
func mySqrt(x int) int {
if x == 0 {
return 0
}
ans := int(math.Exp(0.5 * math.Log(float64(x))))
if (ans+1) * (ans+1) <= x {
return ans+1
}
return ans
}
python3 解法, 执行用时: 32 ms, 内存消耗: 13.4 MB, 提交时间: 2020-11-11 14:45:50
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0: return 0
ans = int(math.exp(0.5 * math.log(x)))
return ans + 1 if (ans+1)**2 <= x else ans
python3 解法, 执行用时: 40 ms, 内存消耗: 13.4 MB, 提交时间: 2020-11-11 14:38:26
class Solution:
def mySqrt(self, x: int) -> int:
return int(math.sqrt(x))