首先，想到的肯定是 Java 中 Math 库自带的 sqrt 函数。
1
2
3
4
5
| class Solution {
public int mySqrt(int x) {
return (int)Math.sqrt(x);
}
}
|
毫无疑问，这是很笨的方法，用时也很长，只超过了 13.84% 的人。
使用二分查找的方法，效率还是不高，只超过了 21.81% 的人。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int mySqrt(int x) {
if(x<=1)
return x;
long start=0;
long end=x/2+1;
long middle=(start+end)/2;
long target=(long)x;
while(start<=end){
long middle2=middle*middle;
if(middle2==x)
return (int)middle;
else if(middle2>x){
if((middle-1)*(middle-1)<x)
return (int)middle-1;
else
end=middle;
}
else{
if((middle+1)*(middle+1)>x)
return (int)middle;
else
start=middle;
}
middle=(start+end)/2;
}
return (int)middle;
}
}
|
参考了一下网上的二分法答案，自愧不如，既简化了运算，也减少了避免了 int 范围的问题，不过效率也不高，只超过了 21.81% 的人。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int mySqrt(int x) {
if(x<=1)
return x;
int start=0;
int end=x/2+1;
while(start<end){
int middle=(start+end)/2;
int div=x/middle;
if(div==middle)
return middle;
else if(div>middle)
start=middle+1;
else
end=middle;
}
return end-1;
}
}
|
高中学过解决这个问题还能使用牛顿法，只要求出牛顿法的迭代公式，一切都会非常简单。迭代公式可以参考Wikipedia-Newton’s method。
参考了博客，写出如下代码（必须使用 double，float 精度不够，会导致一些结果出问题）：
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int mySqrt(int x) {
if(x<=1)
return x;
double last=0;
double res=1;
while(res!=last){
last=res;
res=(res+x/res)/2;
}
return (int)res;
}
}
|
但上面代码效率依旧不高，只击败了 12.23% 的人。