【Leetcode算法题】29. 两数相除

By Long Luo

29. 两数相除题目如下:

  1. 两数相除

给定两个整数,被除数dividend和除数divisor。将两数相除,要求不使用乘法、除法和mod运算符。

返回被除数dividend除以除数divisor得到的商。

整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333…) = truncate(3) = 3

示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333…) = -2

提示:
被除数和除数均为3232位有符号整数。
除数不为00
假设我们的环境只能存储3232位有符号整数,其数值范围是[−2^31, 231−1]。本题中,如果除法结果溢出,则返回231−1。

方法一:暴力法

思路与算法:

首先想到的是不能使用乘法、除法和mod运算符,那么只能使用加减法了。因为除法就是看被除数能让存在多少个被除数相加。因为被除数和除数均为3232位有符号整数,会存在溢出的情况,所以我们首先进行转换,转换成Long型进行处理,代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public int divide(int dividend, int divisor) {
if (dividend == 0) {
return 0;
}

long dividendLong = dividend;
long divisorLong = divisor;

boolean isNegative = false;
if (dividendLong < 0 && divisorLong < 0) {
dividendLong = -dividendLong;
divisorLong = -divisorLong;
} else if (dividendLong < 0 && divisorLong > 0) {
isNegative = true;
dividendLong = -dividendLong;
} else if (dividendLong > 0 && divisorLong < 0) {
isNegative = true;
divisorLong = -divisorLong;
}

long ans = 0;
while (dividendLong >= divisorLong) {
dividendLong -= divisorLong;
ans++;
}

if (isNegative) {
ans = -ans;
}

if (ans > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}

return (int) ans;
}

毫无疑问,超时了!

因为题目规定了“只能存储32位整数”,所以代码中都不能使用任何64位整数。

如果除法结果溢出,那么我们需要返回23112^{31}-1作为答案。因此我们可以首先对于溢出或者容易出错的边界情况进行讨论:

  • 当被除数为3232位有符号整数的最小值231-2^{31}时:
    • 如果除数为11,那么我们可以直接返回答案231-2^{31}
    • 如果除数为1-1,那么答案为2312^{31},产生了溢出。此时我们需要返回23112^{31}-1
  • 当除数为3232位有符号整数的最小值231-2^{31}时:
    • 如果被除数同样为231-2^{31},那么我们可以直接返回答案11
    • 对于其余的情况,我们返回答案00
  • 当被除数为00时,我们可以直接返回答案00

对于一般的情况,根据除数和被除数的符号,我们需要考虑44种不同的可能性。因此,为了方便编码,我们可以将被除数或者除数取相反数,使得它们符号相同。

如果我们将被除数和除数都变为正数,那么可能会导致溢出。例如当被除数为231-2^{31}时,它的相反数2312^{31}产生了溢出。因此,我们可以考虑将被除数和除数都变为负数,这样就不会有溢出的问题,在编码时只需要考虑11种情况了。

如果我们将被除数和除数的其中(恰好)一个变为了正数,那么在返回答案之前,我们需要对答案也取相反数。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public int divide(int dividend, int divisor) {
if (dividend == 0) {
return 0;
}

if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}

int ans = 0;
boolean isNegative = true;
if (dividend > 0 && divisor > 0) {
dividend = -dividend;
isNegative = false;
} else if (dividend > 0 && divisor < 0) {
dividend = -dividend;
divisor = -divisor;
} else if (dividend < 0 && divisor < 0) {
isNegative = false;
divisor = -divisor;
}

while (dividend + divisor <= 0) {
dividend += divisor;
ans++;
}

if (isNegative) {
ans = -ans;
}

return ans;
}

复杂度分析:

  • 时间复杂度:O(X/Y)O(X/Y),其中XX是被除数,XX是除数。
  • 空间复杂度:O(1)O(1)

方法二:二分查找

思路与算法:

我们记被除数为XX,除数为YY,并且XXYY都是负数。我们需要找出X/YX/Y的结果ZZZZ一定是正数或00

根据除法以及余数的定义,我们可以将其改成乘法的等价形式,即:

Z×YX>(Z+1)×YZ \times Y \geq X > (Z+1) \times Y

因此,我们可以使用二分查找的方法得到ZZ,即找出最大的ZZ使得Z×YXZ \times Y \geq X成立。

由于我们不能使用乘法运算符,因此我们需要使用「快速乘」算法得到Z×YZ \times Y的值。

细节

由于我们只能使用3232位整数,因此二分查找中会有很多细节。

首先,二分查找的下界为11,上界为23112^{31} - 1。唯一可能出现的答案为2312^{31}的情况已经被我们在「前言」部分进行了特殊处理,因此答案的最大值为23112^{31} - 1。如果二分查找失败,那么答案一定为00

在实现「快速乘」时,我们需要使用加法运算,然而较大的ZZ也会导致加法运算溢出。例如我们要判断A+BA + B是否小于CC时(其中AA,BB,CC均为负数),A+BA + B可能会产生溢出,因此我们必须将判断改为A<CBA < C - B是否成立。由于任意两个负数的差一定在[231+1,2311][-2^{31} + 1, 2^{31} - 1]范围内,这样就不会产生溢出。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
  public int divide(int dividend, int divisor) {
// 考虑被除数为最小值的情况
if (dividend == Integer.MIN_VALUE) {
if (divisor == 1) {
return Integer.MIN_VALUE;
}
if (divisor == -1) {
return Integer.MAX_VALUE;
}
}
// 考虑除数为最小值的情况
if (divisor == Integer.MIN_VALUE) {
return dividend == Integer.MIN_VALUE ? 1 : 0;
}
// 考虑被除数为 0 的情况
if (dividend == 0) {
return 0;
}

// 一般情况,使用二分查找
// 将所有的正数取相反数,这样就只需要考虑一种情况
boolean rev = false;
if (dividend > 0) {
dividend = -dividend;
rev = !rev;
}
if (divisor > 0) {
divisor = -divisor;
rev = !rev;
}

int left = 1;
int right = Integer.MAX_VALUE;
int ans = 0;
while (left <= right) {
// 注意溢出,并且不能使用除法
int mid = left + ((right - left) >> 1);
boolean check = quickAdd(divisor, mid, dividend);
if (check) {
ans = mid;
// 注意溢出
if (mid == Integer.MAX_VALUE) {
break;
}
left = mid + 1;
} else {
right = mid - 1;
}
}

return rev ? -ans : ans;
}

// 快速乘
public boolean quickAdd(int y, int z, int x) {
// x 和 y 是负数,z 是正数
// 需要判断 z * y >= x 是否成立
int result = 0;
int add = y;
while (z != 0) {
if ((z & 1) != 0) {
// 需要保证 result + add >= x
if (result < x - add) {
return false;
}
result += add;
}
if (z != 1) {
// 需要保证 add + add >= x
if (add < x - add) {
return false;
}
add += add;
}
// 不能使用除法
z >>= 1;
}
return true;
}

复杂度分析:

  • 时间复杂度:O(log2C)O(\log^2 C),其中CC表示3232位整数的范围。二分查找的次数为O(logC)O(\log C),其中的每一步我们都需要O(logC)O(\log C)使用「快速乘」算法判断Z×YXZ \times Y \geq X是否成立,因此总时间复杂度为O(log2C)O(\log^2 C)

  • 空间复杂度:O(1)O(1)