暴力破解求解：使用最直观的解法，性能也符合预期，非常之慢。
class Solution {
public:
int mySqrt(int x) {
int ans = 0;
for(int i = 1;i <= x;i++)
{
//avoid overflow
if(i > x / i)
return ans;
ans = i;
}
return ans;
}
};Runtime: 68 ms, faster than 5.95% of C++ online submissions for Sqrt(x).
Memory Usage: 6.2 MB, less than 100.00% of C++ online submissions for Sqrt(x).看了wikiInteger square root
class Solution {
public:
int mySqrt(int x) {
long long r = x;
while(r * r > x)
{
r = (r + x/r) / 2;
}
return r;
}
};运行时间相对于方法一中提升明显：
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sqrt(x).
Memory Usage: 6.2 MB, less than 100.00% of C++ online submissions for Sqrt(x).二分查找解法:
class Solution {
public:
int mySqrt(int x) {
if(x == 0 || x == 1)
return x;
long long left = 0,right = x;
while(true){
int mid =left + (right -left)/2;
if(mid > x / mid)
right = mid - 1;
else if (mid <= x / mid){
//当前mid * mid <= x,(mid+1)*(mid+1) > x,那么mid就是要查找的答案
if(mid + 1 > x /(mid + 1))
return mid;
left = mid + 1;
}
}
return 0;
}
};运行结果:
Runtime: 4 ms, faster than 55.75% of C++ online submissions for Sqrt(x).
Memory Usage: 6.1 MB, less than 63.26% of C++ online submissions for Sqrt(x).