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

发表于 更新于 分类于 阅读次数： 本文字数： 8.1k 阅读时长 ≈ 7 分钟

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运算符，那么首先想到的是只能使用加减法了。

因为除法就是看被除数能让多少个除数相加，因为被除数和除数均为 3232 位有符号整数，存在溢出的可能，所以我们首先进行类型转换，转换成 Long\textit{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
public int divide(int dividend, int divisor) {
    if (dividend == 0) {
        return 0;
    }

    long dividendLong = dividend;
    long divisorLong = divisor;

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

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

    ans = sign ? -ans : ans;

    return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;
}

毫无疑问，超时了！

卡在了这个 -2147483648 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
public int divide(int dividend, int divisor) {
    if (divisor == Integer.MIN_VALUE) {
        return dividend == Integer.MIN_VALUE ? 1 : 0;
    }
    
    if (dividend == Integer.MIN_VALUE) {
        if (divisor == 1) {
            return dividend;
        } else if (divisor == -1) {
            return Integer.MAX_VALUE;
        }
    } else if (dividend == Integer.MAX_VALUE) {
        if (divisor == 1) {
            return dividend;
        } else if (divisor == -1) {
            return -dividend;
        }
    }

    long dividendLong = dividend;
    long divisorLong = divisor;

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

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

    ans = sign ? -ans : ans;

    return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;
}

因为针对性处理了，所以上述代码 AC 了！

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

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

  • 当被除数为 3232 位有符号整数的最小值 −231-2^{31} 时：
    • 如果除数为 11，那么我们可以直接返回答案 −231-2^{31}；
    • 如果除数为 −1-1，那么答案为 2312^{31}，产生了溢出。此时我们需要返回 231−12^{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
34
35
36
37
public int divide(int dividend, int divisor) {
    if (dividend == Integer.MIN_VALUE) {
        if (divisor == 1) {
            return dividend;
        } else if (divisor == -1) {
            return Integer.MAX_VALUE;
        } else if (divisor == Integer.MIN_VALUE) {
            return 1;
        }
    } else if (dividend == Integer.MAX_VALUE) {
        if (divisor == 1) {
            return dividend;
        } else if (divisor == -1) {
            return -dividend;
        }
    }

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

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

    return sign ? -ans : ans;
}

注意需要增加对 -2147483648 -2147483648 测试用例进行特殊处理，否则会出现超时，因为 -2147483648 取反还是 -2147483648，会出现死循环！

复杂度分析：

  • 时间复杂度：O(X/Y)O(X/Y)，其中 XX 是被除数，YY 是除数。

  • 空间复杂度：O(1)O(1)。

方法二：二分查找

思路与算法：

参考 Illustration of Fast Power Algorithm - Exponentiation by Squaring or Binary Exponentiation ，实现一个类似 quickMul\texttt{quickMul} 的 quickAdd\texttt{quickAdd} 方法。

不考虑溢出情况，设被除数为 XX，除数为 YY，X>0Y>0X \gt 0 Y \gt 0，那么结果 Z=X/Y,0≤Z≤XZ = X/Y, 0 \le Z \le X。

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

Z×Y≤X<(Z+1)×YZ \times Y \le X < (Z+1) \times Y

因此可以使用二分查找在 [0,X][0, X] 中寻找答案，每次循环都可以排除一半。

代码如下所示：

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
public int divide(int dividend, int divisor) {
    long x = dividend;
    long y = divisor;

    boolean sign = false;

    if ((x > 0 && y < 0) || (x < 0 && y > 0)) {
        sign = true;
    }

    if (x < 0) {
        x = -x;
    }

    if (y < 0) {
        y = -y;
    }

    long left = 0;
    long right = x;

    while (left < right) {
        long mid = (left + right + 1) >> 1;
        long result = quickAdd(y, mid);
        if (result <= x) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    long ans = sign ? -left : left;
    if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) {
        return Integer.MAX_VALUE;
    }

    return (int) ans;
}

public long quickAdd(long x, long y) {
    long ans = 0;
    while (y > 0) {
        if ((y & 0x01) == 1) {
            ans += x;
        }

        x += x;
        y = y >> 1;
    }

    return ans;
}

上述代码是需要转换成 long 型进行处理，但题目要求只能使用 3232 位整数，所以我们需要将 XX 和 YY 转换成负数进行处理，和之前公式不同的是：

Z×Y≥X>(Z+1)×Y,0≤Z<XZ \times Y \ge X > (Z+1) \times Y, 0 \le Z < X

使用二分查找找到最大的 ZZ 使得 Z×Y≥XZ \times Y \geq X 成立。

细节

  1. 二分查找的下界为 00，上界为 231−12^{31} - 1。唯一可能出现的答案为 2312^{31} 的情况已经进行了特殊处理，因此答案的最大值为 231−12^{31} - 1。如果二分查找失败，那么答案一定为 00。

  2. 较大的 ZZ 也会导致加法运算溢出。例如要判断 A+BA + B 是否小于 CC 时（其中 A,B,CA, B, C 均为负数），A+BA + B 可能会产生溢出，因此必须将判断改为 A<C−BA < C - B 是否成立。由于任意两个负数的差一定在 [−231+1,231−1][-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
public int divide(int dividend, int divisor) {
    if (divisor == Integer.MIN_VALUE) {
        return dividend == Integer.MIN_VALUE ? 1 : 0;
    }

    if (dividend == 0) {
        return 0;
    }

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

    boolean sign = false;
    if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
        sign = true;
    }

    if (dividend > 0) {
        dividend = -dividend;
    }

    if (divisor > 0) {
        divisor = -divisor;
    }

    int MAX = Integer.MIN_VALUE >> 1;
    int ans = 0;

    // dividend became negative
    while (dividend <= divisor) {
        int temp = divisor;
        int step = -1;

        while (temp >= MAX && step >= MAX && temp >= dividend - temp) {
            temp += temp;
            step += step;
        }

        dividend -= temp;
        ans += step;
    }

    return sign ? ans : -ans;
}

复杂度分析：

  • 时间复杂度：O(logx×logy)O(logx \times logy)，二分查找的次数为 O(logx)O(logx)，其中的每一步我们都需要 O(logy)O(logy) 使用「快速乘」算法判断 Z×Y≥XZ \times Y \ge X 是否成立，因此总时间复杂度为 O(log⁡2C)O(\log^2 C)。

  • 空间复杂度：O(1)O(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
public int divide(int dividend, int divisor) {
    if (divisor == Integer.MIN_VALUE) {
        return dividend == Integer.MIN_VALUE ? 1 : 0;
    }

    if (dividend == 0) {
        return 0;
    }

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

    long x = dividend;
    long y = divisor;

    boolean sign = false;
    if ((x > 0 && y < 0) || (x < 0 && y > 0)) {
        sign = true;
    }

    x = x > 0 ? x : -x;
    y = y > 0 ? y : -y;

    long ans = div(x, y);
    if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) {
        return Integer.MAX_VALUE;
    }

    return (int) (sign ? -ans : ans);
}

public long div(long dividend, long divisor) {
    if (dividend < divisor) {
        return 0;
    }

    long ans = 1;
    long temp = divisor;

    while ((temp + temp) <= dividend) {
        ans = ans << 1;
        temp = temp << 1;
    }

    return ans + div(dividend - temp, divisor);
}

复杂度分析：

  • 时间复杂度：O(logx×logy)O(logx \times logy)，二分查找的次数为 O(logx)O(logx)，其中的每一步我们都需要 O(logy)O(logy) 使用「快速乘」算法判断 Z×Y≥XZ \times Y \geq X 是否成立，因此总时间复杂度为 O(log⁡2C)O(\log^2 C)。

  • 空间复杂度：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. 😉😃💗