int mySqrt(int x) {
int i = 1;
while(i*i <=x)
i++;
return --i;
}
可把你给厉害坏了。脚趾头想也想到了结局。
✘ Runtime Error
✘ 15/1017 cases passed (N/A)
✘ error: Line 43: Char 16: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int' (solution.cpp)
✘ error: Line 43: Char 16: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int' (solution.cpp)
✘ testcase: '2147395600'
二分法
思想,这道题的意思是让我们寻找一个数,这个数是在所有平方小于等于x的数中最大的那一个。
low=0,high=x,满足low<high的条件就循环,将0到x分成两部分,取mid值:
- 若mid^2==x,运气绝了,赶紧返回mid啊!
- 若mid^2>x,则接下来我们应该mid的左半部分查找,即low= mid+1
- 若mid^2<x,则接下来我们应该mid的右半部分(包括mid)查找,即high = mid;
若从循环当中退出,此时应当是low==high,所以我们将其减一后返回。(3,8为例自己推推)
有需要注意的地方,在判断时不能直接做乘法, int会溢出还是时间会超出什么的总之是不行。所以我们选择做除法,但是一旦涉及除法,我们就要想分母是否合法,所以将x<=1的情况单列出来。还有个问题,是在计算mid值的时候,如果直接相加除二,计算量非常大是要超时的,所以也要换种写法。
✔ Accepted ✔ 1017/1017 cases passed (4 ms) ✔ Your runtime beats 100 % of cpp submissions ✔ Your memory usage beats 99.48 % of cpp submissions (8.2 MB)
class Solution {
//二分查找
public:
int mySqrt(int x) {
if(x<=1)
return x;
int low = 1,high = x;
while(low < high){
//int mid = (low+high)/2;
int mid = low + (high-low)/2;
if(mid == x/mid)
return mid;
else if(mid < x/mid)
low = mid+1;
else
high = mid;
}
return low-1;//high-1
}
};