c**z
发帖数: 669 | 1 class Solution {
public:
int sqrt(int x) {
int l = 0;
int r = x;
while( l<=r)
{
int m = l + (r-l)/2;
if ( m*m == x) return m;
else if ( m*m > x)
{
r = m -1;
}
else
{
l = m + 1;
}
}
return -1;
}
}; |
e***m
发帖数: 92 | 2 你的循环中如果r=l+1,某些情况下会出现死循环
【在 c**z 的大作中提到】
: class Solution {
: public:
: int sqrt(int x) {
: int l = 0;
: int r = x;
:
: while( l<=r)
: {
: int m = l + (r-l)/2;
: if ( m*m == x) return m;
|
b******g
发帖数: 3616 | 3 非大牛，也在刷题。
看了你的code发现两个问题：
第一是溢出问题：当x很大时，你的第一轮m*m = x^2/4，很可能就已经溢出了。我想这
是造成为什么会time limit exceeded的原因。将乘法比较改为x/m的除法比较就可以避
免这个问题。
第二个问题：我的理解是这题求的是一个近似平方根，也就是sqrt(17)应该给出的答案
是4.但你的程序似乎对非完全平方数都会返回-1 |
l*****a
发帖数: 14598 | 4 int lo=0;
int hi=x;
int res=-1;
while(lo<=hi) {
int mid=lo+(hi-lo)/2;
if(mid==x/mid) return mid;
if(mid>x/mid) hi=mid-1;
else {
res=mid;
lo=mid+1;
}
}
return res;
【在 c**z 的大作中提到】
: class Solution {
: public:
: int sqrt(int x) {
: int l = 0;
: int r = x;
:
: while( l<=r)
: {
: int m = l + (r-l)/2;
: if ( m*m == x) return m;
|
v****a
发帖数: 236 | 5 LS说得对。
也可以用double 作为中间结果，就不用判断溢出了。
double diff = 0.01;
double m = (low + high) / 2;
if(Math.abs(m*m - x) < diff)
{
return (int)m;
}
else
{
... 二分查找, 注意考虑diff
} |
b******g
发帖数: 3616 | 6 这题我觉得用除法做的时候有个corner case,就是当x为1时， 第一次while循环时mid
就变成0，这样x/mid就有问题了。所以应该要加上一个额外判断。
【在 l*****a 的大作中提到】
: int lo=0;
: int hi=x;
: int res=-1;
: while(lo<=hi) {
: int mid=lo+(hi-lo)/2;
: if(mid==x/mid) return mid;
: if(mid>x/mid) hi=mid-1;
: else {
: res=mid;
: lo=mid+1;
|
l*****a
发帖数: 14598 | 7 嗯，可以先判，0
mid
【在 b******g 的大作中提到】
: 这题我觉得用除法做的时候有个corner case,就是当x为1时， 第一次while循环时mid
: 就变成0，这样x/mid就有问题了。所以应该要加上一个额外判断。
|
r****7
发帖数: 2282 | 8 x = 1就过不去啊
如果不是完全平方数就返回-1，把while换成 l < r
如果是返回最近的那个，m*m == x换成 +/-1分别大于和小于x
【在 c**z 的大作中提到】
: class Solution {
: public:
: int sqrt(int x) {
: int l = 0;
: int r = x;
:
: while( l<=r)
: {
: int m = l + (r-l)/2;
: if ( m*m == x) return m;
|
