[Leetcode][29. 两数相除] 3种方法：暴力法，二分搜索，递归

By Long Luo

Leetcode 29. 两数相除 题目如下：

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$位有符号整数，存在溢出的可能，所以我们首先进行转换，转换成Long型进行处理。

代码如下所示：

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$位整数。

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

• 当被除数为$32$位有符号整数的最小值$-2^{31}$时：
  • 如果除数为$1$，那么我们可以直接返回答案$-2^{31}$；
  • 如果除数为$-1$，那么答案为$2^{31}$，产生了溢出。此时我们需要返回$2^{31}-1$。
• 当除数为$32$位有符号整数的最小值$-2^{31}$时：
  • 如果被除数同样为$-2^{31}$，那么我们可以直接返回答案$1$；
  • 对于其余的情况，我们返回答案$0$。
• 当被除数为$0$时，我们可以直接返回答案$0$。

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

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

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

代码如下所示：

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)$，其中$X$是被除数，$Y$是除数。
• 空间复杂度：$O(1)$。

方法二：二分查找

思路与算法：

我们记被除数为$X$，除数为$Y$，并且$X$和$Y$都是负数。我们需要找出$X/Y$的结果$Z$。$Z$一定是正数或$0$。

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

$Z \times Y \geq X > (Z+1) \times Y$

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

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

细节

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

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

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

代码如下所示：

  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(\log^2 C)$，其中$C$表示$32$位整数的范围。二分查找的次数为$O(\log C)$，其中的每一步我们都需要$O(\log C)$使用「快速乘」算法判断$Z \times Y \geq X$是否成立，因此总时间复杂度为$O(\log^2 C)$。
• 空间复杂度：$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. 😉😃💗