实现 int sqrt(int x)
函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4 输出: 2
示例 2:
输入: 8 输出: 2 说明: 根号 8 是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
注意:本题与主站 69 题相同: https://leetcode.cn/problems/sqrtx/
二分查找。
class Solution:
def mySqrt(self, x: int) -> int:
left, right = 0, x
while left < right:
mid = (left + right + 1) >> 1
# mid*mid <= x
if mid <= x // mid:
left = mid
else:
right = mid - 1
return left
class Solution {
public int mySqrt(int x) {
int left = 0, right = x;
while (left < right) {
int mid = (left + right + 1) >>> 1;
if (mid <= x / mid) {
// mid*mid <= x
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
}
class Solution {
public:
int mySqrt(int x) {
long long left = 0, right = x;
while (left < right) {
long long mid = left + ((right - left + 1) >> 1);
if (mid <= x / mid)
left = mid;
else
right = mid - 1;
}
return (int)left;
}
};
func mySqrt(x int) int {
left, right := 0, x
for left < right {
mid := left + (right-left+1)>>1
if mid <= x/mid {
left = mid
} else {
right = mid - 1
}
}
return left
}
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function (x) {
let left = 0;
let right = x;
while (left < right) {
const mid = (left + right + 1) >>> 1;
if (mid <= x / mid) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
};
public class Solution {
public int MySqrt(int x) {
int left = 0, right = x;
while (left < right)
{
int mid = left + right + 1 >> 1;
if (mid <= x / mid)
{
left = mid;
}
else
{
right = mid - 1;
}
}
return left;
}
}