69. x 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
相乘穷举，可能溢出
intmySqrt(intx) {
if (x==0) return0;
if (x<=3) return1;
inti=2;//输入2147395600时报错，（i*i）也是个int， //int，可保存不了这么大的数字，只好改为 //long
for (; i<x/2; ++i)
{
if ( (i*i<=x) && ((i+1)* (i+1) >x))
returni;
}
returni;
}
intmySqrt(intx) {
if (x==0) return0;
if (x<=3) return1;
longinti=2;//改为long后通过
for (; i<x/2; ++i)
{
if ( (i*i<=x) && ((i+1)* (i+1) >x))
returni;
}
returni;
}
执行用时 :64 ms, 在所有 C++ 提交中击败了5.00%的用户
内存消耗 :8.1 MB, 在所有 C++ 提交中击败了90.43%的用户
二分法会更快一点
intmySqrt(intx) {
if (x==0) return0;
if (x<=3) return1;
intmin=0;
intmax=x;
while (max-min>1)
{
intm= (max+min) /2;
if (x/m<m)//用x/m<m，而不是m*m<x可以防止溢出
max=m;
else
min=m;
}
returnmin;
}
intmySqrt(intx) {
longmid=0;
longleft=0;
longright=x;
while (left<right)
{
mid= (left+right+1) /2;
longsq=mid*mid; //或者这样也会更快一点
if (sq>x)
{
right=mid-1;
}
else
{
left=mid;
}
}
return (int)left;
}
