Sqrt(x)
思路一: 暴力
public int mySqrt(int x) {
long begin = 1L;
while ((begin * begin) <= x) {
begin++;
}
return Long.valueOf(begin).intValue() - 1;
}
思路二: 二分法,在 [1, x] 范围内寻找求解,
二分的中值 mid 完全分类,只可能出现三种情况
- mid * mid == x,直接返回
- mid * mid < x,记录 mid 值,继续寻找
- mid * mid > x,继续寻找
因为求解需要舍去小数部分,所以我们只记录情况一和情况二的 mid 就能覆盖求解
public int mySqrt(int x) {
int low = 1;
int high = x;
int result = -1;
while (low < high) {
int mid = (low + high) >>> 1;
if ((long) mid * mid <= x) {
result = mid;
low = mid+1;
} else {
high = mid - 1;
}
}
return result;
}
标签:begin,求解,int,mid,high,low,easy,69,leetcode
From: https://www.cnblogs.com/iyiluo/p/16785603.html