leetcode 69: x的平方根
原题描述 leetcode 69
作者：danmo_wuhen
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
从i = 2开始不断叠加，计算i*i的值，一旦出现i*i>x的情况，就跳出循环。需要注意i*i结果的超出int型范围的情况。
public int mySqrt(int x) {
if(x < 2) return x;
long i = 2;
for (; i x) break;
}
return (int)i - 1;
}
该解法简单容易想到，但是显然效率不高，比如当x = 2147395600时，结果为46340，也就是说循环需要执行4万多次。时间复杂度是O(n12n^\frac{1}{2}n21)，空间复杂度O(1)。
解法二（牛顿法）牛顿法的公式是：xn+1=xn+f(xn)f′(xn)x_{n+1} = x_{n}+\frac{f(x_{n})}{{f}'(x_{n})}xn+1=xn+f′(xn)f(xn)
求解x2=nx^2 = nx2=n就是求：f(x)=x2−n=0f(x) = x^2 - n = 0f(x)=x2−n=0的根。带入上面公式得到：xi+1=xi+xi2−n2xi=12(xi+nxi)x_{i+1} = x_{i}+\frac{x_i^2 - n}{2x_i} =\frac{1}{2}(x_i+\frac{n}{x_i})xi+1=xi+2xixi2−n=21(xi+xin)
对于本题，因为只是求其整数部分，所以当误差小于1时结束迭代。
public int mySqrt(int x) {
if(x =1){
x0 = x1;
x1 = (x0 + x/x0)/2;
}
return (int)x1;
}
时间复杂度O(log(n))，空间复杂度O(1)，
作者：danmo_wuhen
