GuilinDev
Lc0069
05 August 2008
69 Sqrt(x)
原题概述
Implement 1
int sqrt(int x)
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
1
2
Input: 4
Output: 2
Example 2:
1
2
3
4
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
题意和分析
求平方根，保证输入是正数，向下返回值。
1）用二分搜索来在[0,x]之间找平方根，找到一个不大于目标值的数；
2）使用牛顿迭代法，这个主要是逼近法求方程的根（http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html），这里是求x^2的解，因此方程f(x) = x^2 - n， 相当于求解f(x)=0的解，如图所示
首先取x0，如果x0不是解，做一个经过(x0,f(x0))这个点的切线，与x轴的交点为x1。
同样的道理，如果x1不是解，做一个经过(x1,f(x1))这个点的切线，与x轴的交点为x2。
以此类推。
以这样的方式得到的xi会无限趋近于f(x)=0的解。
判断xi是否是f(x)=0的解有两种方法：
一是直接计算f(xi)的值判断是否为0，二是判断前后两个解xi和xi-1是否无限接近。
经过(xi, f(xi))这个点的切线方程为f(x) = f(xi) + f’(xi)(x - xi)，其中f’(x)为f(x)的导数，本题中为2x。令切线方程等于0，即可求出xi+1=xi - f(xi) / f’(xi)。
继续化简，xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2。
代码
二分法搜索合适的数，模板写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int mySqrt(int x) {
if (x <= 1) {
return x;
}
int left = 0, right = x;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
int temp = x / mid;
if (temp >= mid) { // 等于时还不能停，因为是地板除法，temp*mid可能比x小（有更大的备选），所以要挪动left
left = mid;
} else {
right = mid;
}
}
if (x / right >= right) { // 先检查right是否符合，因为right更大
return right;
}
return left;
}
}
牛顿迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
double last = 0;
double result = 1;
while (result != last) {
last = result;
result = (result + x / result) / 2;
}
return (int)result;
}
}