By Long Luo
Leetcode 29. 两数相除 题目如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 29. 两数相除 给定两个整数,被除数`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 提示: 被除数和除数均为$32$位有符号整数。 除数不为$0$。 假设我们的环境只能存储$32$位有符号整数,其数值范围是[−2^31, 2^31−1]。本题中,如果除法结果溢出,则返回2^31−1。
方法一:暴力法
思路与算法:
因为题目要求不能使用乘法、除法和mod
运算符 ,那么首先想到的是只能使用加减法 了。
因为除法就是看被除数能让多少个除数相加,因为被除数和除数均为32 32 3 2 位有符号整数,存在溢出的可能,所以我们首先进行转换,转换成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 32 3 2 位整数”,所以代码中都不能使用任何64 64 6 4 位整数。
如果除法结果溢出,那么我们需要返回2 31 − 1 2^{31}-1 2 3 1 − 1 作为答案。因此我们可以首先对于溢出或者容易出错的边界情况进行讨论:
当被除数为32 32 3 2 位有符号整数的最小值− 2 31 -2^{31} − 2 3 1 时:
如果除数为1 1 1 ,那么我们可以直接返回答案− 2 31 -2^{31} − 2 3 1 ;
如果除数为− 1 -1 − 1 ,那么答案为2 31 2^{31} 2 3 1 ,产生了溢出。此时我们需要返回2 31 − 1 2^{31}-1 2 3 1 − 1 。
当除数为32 32 3 2 位有符号整数的最小值− 2 31 -2^{31} − 2 3 1 时:
如果被除数同样为− 2 31 -2^{31} − 2 3 1 ,那么我们可以直接返回答案1 1 1 ;
对于其余的情况,我们返回答案0 0 0 。
当被除数为0 0 0 时,我们可以直接返回答案0 0 0 。
对于一般的情况,根据除数和被除数的符号,我们需要考虑4 4 4 种不同的可能性。因此,为了方便编码,我们可以将被除数或者除数取相反数,使得它们符号相同。
如果我们将被除数和除数都变为正数,那么可能会导致溢出。例如当被除数为− 2 31 -2^{31} − 2 3 1 时,它的相反数2 31 2^{31} 2 3 1 产生了溢出。因此,我们可以考虑将被除数和除数都变为负数,这样就不会有溢出的问题,在编码时只需要考虑1 1 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 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) O ( X / Y ) ,其中X X X 是被除数,Y Y Y 是除数。
空间复杂度:O ( 1 ) O(1) O ( 1 ) 。
方法二:二分查找
思路与算法:
我们记被除数为X X X ,除数为Y Y Y ,并且X X X 和Y Y Y 都是负数。我们需要找出X / Y X/Y X / Y 的结果Z Z Z 。Z Z Z 一定是正数或0 0 0 。
根据除法以及余数的定义,我们可以将其改成乘法的等价形式,即:
Z × Y ≥ X > ( Z + 1 ) × Y Z \times Y \geq X > (Z+1) \times Y
Z × Y ≥ X > ( Z + 1 ) × Y
因此,我们可以使用二分查找的方法得到Z Z Z ,即找出最大的Z Z Z 使得Z × Y ≥ X Z \times Y \geq X Z × Y ≥ X 成立。
由于我们不能使用乘法运算符,因此我们需要使用「快速乘」算法得到Z × Y Z \times Y Z × Y 的值。
细节
由于我们只能使用32 32 3 2 位整数,因此二分查找中会有很多细节。
首先,二分查找的下界为1 1 1 ,上界为2 31 − 1 2^{31} - 1 2 3 1 − 1 。唯一可能出现的答案为2 31 2^{31} 2 3 1 的情况已经被我们在「前言」部分进行了特殊处理,因此答案的最大值为2 31 − 1 2^{31} - 1 2 3 1 − 1 。如果二分查找失败,那么答案一定为0 0 0 。
在实现「快速乘」时,我们需要使用加法运算,然而较大的Z Z Z 也会导致加法运算溢出。例如我们要判断A + B A + B A + B 是否小于C C C 时(其中A A A ,B B B ,C C C 均为负数),A + B A + B A + B 可能会产生溢出,因此我们必须将判断改为A < C − B A < C - B A < C − B 是否成立。由于任意两个负数的差一定在[ − 2 31 + 1 , 2 31 − 1 ] [-2^{31} + 1, 2^{31} - 1] [ − 2 3 1 + 1 , 2 3 1 − 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 ; } 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) { int result = 0 ; int add = y; while (z != 0 ) { if ((z & 1 ) != 0 ) { if (result < x - add) { return false ; } result += add; } if (z != 1 ) { if (add < x - add) { return false ; } add += add; } z >>= 1 ; } return true ; }
复杂度分析:
时间复杂度:O ( log 2 C ) O(\log^2 C) O ( log 2 C ) ,其中C C C 表示32 32 3 2 位整数的范围。二分查找的次数为O ( log C ) O(\log C) O ( log C ) ,其中的每一步我们都需要O ( log C ) O(\log C) O ( log C ) 使用「快速乘」算法判断Z × Y ≥ X Z \times Y \geq X Z × Y ≥ X 是否成立,因此总时间复杂度为O ( log 2 C ) O(\log^2 C) O ( log 2 C ) 。
空间复杂度:O ( 1 ) O(1) O ( 1 ) 。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions . 😉😃💗