【刷穿 LeetCode】29. 两数相除 : 对限制条件的两种理解，以及两种倍增实现

题目描述

这是 LeetCode 上的 29. 两数相除 ，难度为 中等。

Tag : 「数学」、「二分」

给定两个整数，被除数 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}231,  2^{31}231 − 1]。本题中，如果除法结果溢出，则返回 2^{31}231 − 1。

基本分析

主要的歧义在于第三点限制「假设我们的环境只能存储 3232 位有符号整数，其数值范围是 [−2^{31}, 2^{31} − 1][−231,231−1]。本题中，如果除法结果溢出，则返回 2^{31} − 1231−1」的理解。

该限制有两种理解方式：

1. 不限制算法使用 long，只是解释为什么在溢出时，返回 2^{31} − 1231−1；
2. 限制算法使用 long。

原始题解在 这里 。

理解一（不限制 long）

当不限制使用 long 时，基本思路为：

• 首先，dividend 和 divisor 均有「正数」和「负数」两种可能，当且仅当其中一者为负数时，结果为负，为了方便，我们可以先记录最终结果的正负号，然后将 dividend 和 divisor 都当成正数来处理；
• 现在两者都满足 x >= 0x>=0，然后利用 dividend 和 divisor 均为 int，可以确定答案的绝对值落在 [0, dividend][0,dividend] 范围内（当且仅当 divisor 是范围在 [0, 1][0,1] 的浮点数时，答案会大于 dividend）；
• 假设答案为xx，那么在以xx为分割点的整数数轴上，具有「二段性」，因此我们可以二分找到该分割点：

• 大于 xx 的数 yy 满足 y * b > ay∗b>a；
• 小于等于 xx 的数 yy 满足 y * b <= ay∗b<=a；

• 根据「二段性」分析，我们发现二分的 check 实现需要用到乘法，因此我们需要实现一个「不用乘法符号」的乘法实现（这可以使用倍增思想来实现 mul 操作）。

代码：

class Solution {
    int INF = Integer.MAX_VALUE;
    public int divide(int _a, int _b) {
        long a = _a, b = _b;
        boolean flag = false;
        if ((a < 0 && b > 0) || (a > 0 && b < 0)) flag = true;
        if (a < 0) a = -a;
        if (b < 0) b = -b;
        long l = 0, r = a;
        while (l < r) {
            long mid = l + r + 1 >> 1;
            if (mul(mid, b) <= a) l = mid;
            else r = mid - 1;
        }
        r = flag ? -r : r;
        if (r > INF || r < -INF - 1) return INF;
        return (int)r;
    }
    long mul(long a, long k) {
        long ans = 0;
        while (k > 0) {
            if ((k & 1) == 1) ans += a;
            k >>= 1;
            a += a;
        }
        return ans;
    }
}
复制代码

• 时间复杂度：在 [0, a][0,a] 范围内二分操作，复杂度为O(\log{a})O(loga)；倍增乘法的与操作数的二进制长度相关，复杂度为 O(\log{b})O(logb)。整体复杂度为 O(\log{a} * \log{b})O(loga∗logb)
• 空间复杂度：O(1)O(1)

理解二（限制 long）

对于全程不使用 long 的做法，我们需要将所有数映射到负数进行处理（以 00 为分割点，负数所能表示的范围更大）。

基本思路为：

• 起始先对边界情况进行特判；
• 记录最终结果的符号，并将两数都映射为负数；
• 可以预处理出倍增数组，或采取逐步增大 dividend 来逼近 divisor 的方式。

由于操作数都是负数，因此自倍增过程中，如果操作数小于 INT_MIN 的一半（-1073741824），则代表发生溢出。

代码：

class Solution {
    int MIN = Integer.MIN_VALUE, MAX = Integer.MAX_VALUE;
    int LIMIT = -1073741824; // MIN 的一半
    public int divide(int a, int b) {
        if (a == MIN && b == -1) return MAX;
        boolean flag = false;
        if ((a > 0 && b < 0) || (a < 0 && b > 0)) flag = true;
        if (a > 0) a = -a;
        if (b > 0) b = -b;
        int ans = 0;
        while (a <= b){
            int c = b, d = -1;
            while (c >= LIMIT && d >= LIMIT && c >= a - c){
                c += c; d += d;
            }
            a -= c;
            ans += d;
        }
        return flag ? ans : -ans;
    }
}
复制代码

• 时间复杂度：O(\log{a} * \log{b})O(loga∗logb)
• 空间复杂度：O(1)O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.29 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。