Implement int sqrt(int x).
Compute and return the square root of x.
一刷
题解：
二分法
Time Complexity - O(logn)， Space Complexity - O(1)
public class Solution {
public int mySqrt(int x) {
if(x<=1) return x;
int lo = 0, hi = x;
while(lo<=hi){
int mid = lo + (hi - lo)/2;
if(mid == x/mid) return mid;
else if(mid < x/mid) lo = mid+1;
else hi = mid-1;
}
return hi;
}
}
牛顿法
x^2 = a(a为input, x为root), 则转化为方程y = x^2 - a，根据转移逼近方程，xn+1 = xn - f(x) / f'(x)，则有xn+1 = (xn + a / xn) / 2
public class Solution {
public int mySqrt(int x) {
if (x <= 1) {
return x;
}
double lastY = x / 2;
double y = (lastY + x / lastY) / 2;
while (y - lastY != 0) {
lastY = y;
y = (lastY + x / lastY) / 2;
}
return (int)y;
}
}
