leetcode 69题
求x的算术平方根。例如4的算术平方根是2。 8的算术平方根也是2(取整)。9的算术平方根是3。
注意的点
- 使用二分查找法,(递归和while循环)
- 二分查找是先比较mid与目标值的大小,而不是先比较两端left和right。
- 节省内存:少新建变量
- 节省内存:用窄类型,例如用byte替换int。
- 减少执行用时:优化算法。
递归实现
public class Test {
public static void main(String[] args) {
System.out.println(mySqrt(2));
System.out.println(mySqrt(3));
int x = 2147483647;
System.out.println(mySqrt(x));
}
public static int mySqrt(int x) {
if (x == 0) {
return 0;
}
if (x == 1) {
return 1;
}
return count(1, x, x);
}
public static int count(int left, int right, int x) {
// System.out.println("start:" + left + " " + right);
int mid = left + (right - left) / 2; //防止(left+right)溢出
if (mid == x / mid) {//防止溢出用除法
return mid;
} else if (mid < x / mid) {//mid*mid<x
if ((mid + 1) > x / (mid + 1)) { //(mid+1)*(mid+1)>x
return mid;
} else {
return count(mid + 1, right, x);
}
} else if (mid > x / mid) {//mid*mid>x
return count(left, mid - 1, x);
}
System.out.println("error");
return -1;
}
}
while循环实现
public class Test2 {
public static void main(String[] args) {
System.out.println(mySqrt(2));
System.out.println(mySqrt(8));
// System.out.println(mySqrt(2147483647));
}
public static int mySqrt(int x) {
// 特殊值判断
if (x == 0) {
return 0;
}
if (x == 1) {
return 1;
}
int left = 1;
int right = x;
// 在区间 [left..right] 查找目标元素
while (left <= right) {
int mid = left + (right - left) / 2;
// System.out.println("开始:left:" + left + " right:" + right + " mid:" + mid);
if (mid > x / mid) { // 注意:这里为了避免乘法溢出,改用除法
right = mid - 1; // 下一轮搜索区间是 [left..mid - 1]
} else if (mid == x / mid) {
return mid;
} else {
// 下一轮搜索区间是 [mid+1..right]
left = mid + 1;
}
// System.out.println("结束:left:" + left + " right:" + right);
}
return left - 1;
}
}
网友评论