h******i
发帖数: 30 | 1 除2个整数不能用乘除.那位给个O(lgn)的解法阿？我只知道O(n)的 |
r*******n
发帖数: 266 | 2 如果是m/n
那start from x=m
step = m/2
loop:
if x * n > m
x = x - step/2
else:
x = x + step/2
step /= 2
基本就是个对分查找
【在 h******i 的大作中提到】
: 除2个整数不能用乘除.那位给个O(lgn)的解法阿？我只知道O(n)的
|
h******i
发帖数: 30 | 3 这个我也想到了 不过题目要求不能用乘法。 x*n>m不合要求阿。 |
r*******n
发帖数: 266 | 4 可以位移和加法啊.....
不还是binary search咩
【在 h******i 的大作中提到】
: 这个我也想到了 不过题目要求不能用乘法。 x*n>m不合要求阿。
|
c****p
发帖数: 6474 | 5 对于x/y，
先找到k，使2^k<=x<2^(k+1)，
x -= 2^k
然后依次比较x和2^(k-1)...2^0至x为零为止。
结果的每一位，如果够减就是1，不够减就是0【 在 happylii (小马哥) 的大作中提到 |
h******i
发帖数: 30 | 6 照着写了个code 不过放在leetcode上测试连small set都超时了。那位给贴个效率高的
，让我学习一下。
int Multiply(int x, int y)
{
bool neg = (x>0&&y<0)||(x<0&&y>0);
y = abs(y);
int res = 0;
int orgy = y;
while(y>1)
{
res += x << 1;
y-=2;
}
if(y==1)
res+=x;
if(neg&&orgy<0)
return -res;
else
return res;
}
int divide(int dividend, int divisor) {
int res = dividend;
int step = dividend;
while(1)
{
int product = Multiply(res,divisor);
if(step>1)
step=step>>1;
if(product>dividend)
{
res-=step;
}
else if((product+divisor)
res+=step;
else
break;
}
return res;
} |
p*****2
发帖数: 21240 | 7 int divide(int dividend, int divisor) {
if (divisor == 0)
throw new ArithmeticException();
int k = 0;
long a = dividend;
long b = divisor;
a = Math.abs(a);
b = Math.abs(b);
boolean neg = (dividend & 1 << 31 ^ divisor & 1 << 31) != 0;
while (b << k <= a)
k++;
int r = 0;
for (int i = k; i >= 0; i--) {
if (b << i > a)
continue;
else {
r |= 1 << i;
a -= b << i;
}
}
return neg ? -r : r;
} |
h******i
发帖数: 30 | 8 刚才在oj上试了下，还是超时了。。。。
【在 p*****2 的大作中提到】
: int divide(int dividend, int divisor) {
: if (divisor == 0)
: throw new ArithmeticException();
: int k = 0;
: long a = dividend;
: long b = divisor;
: a = Math.abs(a);
: b = Math.abs(b);
: boolean neg = (dividend & 1 << 31 ^ divisor & 1 << 31) != 0;
: while (b << k <= a)
|
p*****2
发帖数: 21240 | 9
我在leetcode上试了。可以。
【在 h******i 的大作中提到】
: 刚才在oj上试了下，还是超时了。。。。
|
t****t
发帖数: 6806 | 10 你这乘法是线性的, 能不超时吗.
【在 h******i 的大作中提到】
: 照着写了个code 不过放在leetcode上测试连small set都超时了。那位给贴个效率高的
: ，让我学习一下。
: int Multiply(int x, int y)
: {
: bool neg = (x>0&&y<0)||(x<0&&y>0);
: y = abs(y);
: int res = 0;
: int orgy = y;
: while(y>1)
: {
|
c****p
发帖数: 6474 | |
