首页 > 代码库 > Sqrt(int x) leetcode java
Sqrt(int x) leetcode java
Reference: http://blog.csdn.net/lbyxiafei/article/details/9375735
题目:
Implement int sqrt(int x)
.
Compute and return the square root of x.
题解:
这道题很巧妙的运用了二分查找法的特性,有序,查找pos(在这道题中pos=value),找到返回pos,找不到返回邻近值。
因为是求数x(x>=0) 的平方根, 因此,结果一定是小于等于x且大于等于0,所以用二分查找法肯定能搜到结果。
以每一次的mid的平方来与target既数x相比:
如果mid*mid == x,返回mid;
如果mid*mid < x,那么说明mid过小,应让low = mid+1,在右边继续查找
如果mid*mid > x,那么说明mid过大,应让high = mid-1,在左边继续查找
若x无法开整数根号(在上述查找中没有找到),那么我们仍然可以利用之前对二分查找法总结的技巧,当target值不在数组中,low指向大于target的那个值,high指向小于target的那个值,由于我们需要向下取整的结果,所以我们返回high指向的值(这里high指向的值和high的值是同一个值),这个值就是所求得最接近起开根号结果的整数值。
因为leetcode的test case x=2147395599,在算mid*mid的时候造成溢出,所以mid不能使用int型来接,要使用long型防止溢出(Java中Integer型的范围:-2147483648 到2147483648)
代码为:
1 public int sqrt(int x) {
2 int low = 0;
3 int high = x;
4 while(low<=high){
5 long mid = (long)(low + high)/2;
6 if(mid*mid < x)
7 low = (int)mid + 1;
8 else if(mid*mid > x)
9 high = (int)mid - 1;
10 else
11 return (int)mid;
12 }
13 return high;
14 }
2 int low = 0;
3 int high = x;
4 while(low<=high){
5 long mid = (long)(low + high)/2;
6 if(mid*mid < x)
7 low = (int)mid + 1;
8 else if(mid*mid > x)
9 high = (int)mid - 1;
10 else
11 return (int)mid;
12 }
13 return high;
14 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。