一、题目
1、算法题目
“给定两个整数，进行相除，不能使用乘法、除法和mod运算符。”
题目链接：
来源：力扣（LeetCode）
链接：29. 两数相除 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给定两个整数，被除数 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 复制代码
二、解题
1、思路分析
这个题首先需要考虑整数溢出或边界情况：
当被除数为最小值-232时：
- 除数为1，可以直接返回答案-232。
- 除数为-1，那么答案为232，产生了溢出，需要返回232-1
当除数为最小值-232时：
- 除数同样为-232，返回答案1
- 其他情况，返回0
当除数为0时，返回0。
然后，记被除数和除数为X和Y，结果为Z，使用二分查找法，得到X/Y的最大结果Z，即使得Z x Y ≥ Z成立。
Z x Y的值，可以使用快速乘方法得到。
2、代码实现
代码参考：
public class Solution { public int Divide(int dividend, int divisor) { // 考虑被除数为最小值的情况 if (dividend == int.MinValue) { if (divisor == 1) { return int.MinValue; } if (divisor == -1) { return int.MaxValue; } } // 考虑除数为最小值的情况 if (divisor == int.MinValue) { return dividend == int.MinValue ? 1 : 0; } // 考虑被除数为 0 的情况 if (dividend == 0) { return 0; } // 一般情况，使用二分查找 // 将所有的正数取相反数，这样就只需要考虑一种情况 bool rev = false; if (dividend > 0) { dividend = -dividend; rev = !rev; } if (divisor > 0) { divisor = -divisor; rev = !rev; } int left = 1, right = int.MaxValue, ans = 0; while (left <= right) { // 注意溢出，并且不能使用除法 int mid = left + ((right - left) >> 1); bool check = quickAdd(divisor, mid, dividend); if (check) { ans = mid; // 注意溢出 if (mid == int.MaxValue) { break; } left = mid + 1; } else { right = mid - 1; } } return rev ? -ans : ans; } // 快速乘 public bool quickAdd(int y, int z, int x) { // x 和 y 是负数，z 是正数 // 需要判断 z * y >= x 是否成立 int result = 0, 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; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(log2 C)
其中 C 表示 32 位整数的范围。二分查找的次数为 O(logC)，其中的每一步我们都需要 O(logC) 使用「快速乘」算法判断 Z×Y≥X 是否成立，因此总时间复杂度为 O(log2 C)
空间复杂度： O(1)
只用到常数级的变量。
三、总结
如果我们将被除数和除数的其中（恰好）一个变为了正数，那么在返回答案之前，我们需要对答案也取相反数。
