Sunday, January 6, 2013

[LeetCode] Sqrt(x) 解题报告


Implement int sqrt(int x).
Compute and return the square root of x.
» Solve this problem

[解题思路]
二分法。但是这题有意思的是,二分过程中终止条件的确认。因为整数的乘法有可能导致溢出,而这种溢出的检测跟整数加法直接判断是否小于0是不同的,因为整数的乘法有可能引起多次溢出,当奇数次溢出时是负数,但是偶数次溢出时就又变回正数了,比如
2147395599
如果用是否小于0来终止二分的话,它的平方根会返回617921965,而不是46339。

所以,二分的终点确定比较重要,在运算中想通过是否小于0来判断溢出,是不可靠的,最好的办法就是在二分之前,要求end小于sqrt(INT_MAX)。sqrt(INT_MAX)是个常量,所以不算cheat。
1:    int sqrt(int x) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int start =0, end;  
5:      end= x/2<std::sqrt(INT_MAX)? x/2+1:std::sqrt(INT_MAX);  
6:      while(start<= end)  
7:      {  
8:        int mid = (start+end)/2;  
9:        int sqr = mid*mid;  
10:        if(sqr ==x)  
11:        {  
12:          return mid;  
13:        }  
14:        if(sqr<x)  
15:        {  
16:          start = mid+1;  
17:        }  
18:        else  
19:        {  
20:          end = mid-1;  
21:        }  
22:      }  
23:      return (start+end)/2;  
24:    }  

上网搜了一下,更快的方法是牛顿迭代,不过这个太偏数学了。详情见http://www.2cto.com/kf/201206/137256.html
牛顿迭代法
1:       const float EPS = 0.000000001;  
2:       int sqrt(int x) {  
3:            // Start typing your C/C++ solution below  
4:            // DO NOT write int main() function  
5:            if(x==0) return x;  
6:            float dividend = x;  
7:            float val = x;//最终  
8:            float last;//保存上一个计算的值  
9:            do  
10:            {  
11:                 last = val;  
12:                 val =(val + dividend/val) / 2;  
13:            }while(abs(val-last) > EPS);  
14:            int result = val;  
15:            if(result * result > x)  
16:                 result--;  
17:            return result;  
18:       }  

[Note]
1. Line 15 & 16
虽然设置了迭代精度是EPS,但是始终会有迭代溢出的问题。如果漏了这两句的话,在测试2147395599的时候,会返回46340,而不是46339

4 comments:

harry said...
This comment has been removed by the author.
harry said...

我也写了一个牛顿迭代法,貌似不需要特殊处理溢出的情况
class Solution {
public:
int sqrt(int x) {
if (x ==0)
return 0;
double pre_t;
double cur_t = 1;
do
{
pre_t = cur_t;
cur_t = x / (2 * pre_t) + pre_t / 2.0;
}while(abs(cur_t - pre_t) > 0.00001);
return int(cur_t);
}
};

harry said...

恩,我用了double...精度比float更高,所以没出溢出问题。

codingtmd said...

嗯哪