Implement int sqrt(int x)
.
Compute and return the square root of x.
解题思路1,o(log(n)):
像这种从初始遍历查找匹配的任务,往往可以使用二分法逐渐缩小范围;
初始从0~x/2 + 1,然后逐渐以二分思想缩小查找范围。
解题思路2:
牛顿迭代法(百度百科)
一些小优化:
1、不需要等到Ni * Ni 无限接近于x时,再确定Ni是返回值。
根据牛顿迭代法图解发现,Ni+1 和 Ni不断迭代求解过程中,差距越来越小。
当int(Ni+1) == int(Ni)时,说明迭代结果永远会处于int(Ni+1)和int(Ni+1)+1之间;
因此,由于转换类型自动向下取整,就已经可以确定int(Ni+1)是要求的返回值;
2、初始不必设置为N0 = X,可以从N0 = X/2+1,开始迭代。注意保持N0*N0 > X,否则不仅增加了迭代次数,并且不利于编程;
class Solution {
public:
int mySqrt(int x) {
double ans = x / + ;
int pre = int(ans);
while (ans * ans > x) {
ans = x / ( * ans) + ans / ;
if (pre == int(ans))
break;
else
pre = ans;
}
return pre;
}
};
其他注意点:
1、往往对于int间求值,多考虑int越界问题;
2、遍历查找,多考虑二分的方法;