题目描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

1
2
3
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:

1
2
3
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示：

  • 被除数和除数均为 32 位有符号整数。
  • 除数不为 0。
  • 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

来源：力扣（LeetCode）

题解

根据题目描述，要求我们模拟除法，不可以使用乘法、除法和 mod 运算符。根据除法的定义，我们知道可以使用减法模拟除法，即循环减去 divisor，统计循环次数即可，但是这样做会 超出时间限制，最差的情况需要进行 2^31 运算。可以利用快速乘法 / 倍增降低时间复杂度。

二分查找 + 快速乘法

计算结果的取值范围为 [0, Integer.MAX_VALUE]，所以使用二分查找不断地寻找结果，然后通过快速乘法进行 check，判断 mid * divisor 是否大于等于 dividend（为了防止溢出，所以将正数转换为负数进行计算，故而这里是大于等于）。

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
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, right = Integer.MAX_VALUE, ans = 0;
    while (left <= right) {
        // 注意溢出, 并且不能使用除法
        int mid = left + ((right - left) >> 1);
        boolean check = quickMul(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 quickMul(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;
}
  • 时间复杂度： O(log^2C)*，其中 C 表示 32 位整数的范围。二分查找的次数为 *O(logC)*，其中的每一步我们都需要 *O(logC) 使用「快速乘」算法判断 Z × Y ≥ X 是否成立，因此总时间复杂度为 *O(log^2C)*。
  • 空间复杂度： O(1)

submissions-2022090901

类二分查找（倍增）

DivideTwoIntegers

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
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;
    }

    List<Integer> candidates = new ArrayList<>();
    candidates.add(divisor);
    int index = 0;
    // 注意溢出
    // 因为 dividend 与 divisor 都已经转换为负数, 所以相应的判断都是基于负数的基础上
    while (candidates.get(index) >= dividend - candidates.get(index)) {
        candidates.add(candidates.get(index) + candidates.get(index));
        ++index;
    }
    int ans = 0;
    for (int i = candidates.size() - 1; i >= 0; --i) {
        if (candidates.get(i) >= dividend) {
            ans += 1 << i;
            dividend -= candidates.get(i);
        }
    }

    return rev ? -ans : ans;
}
  • 时间复杂度： O(logC)*，即为二分查找需要的时间。方法二时间复杂度优于方法一的原因是：方法一的每一步二分查找都需要重新计算 Z × Y 的值，需要 *O(logC) 的时间复杂度；而方法二的每一步的权重都是 2 的幂，在二分查找开始前就都是已知的值，因此我们可以在 O(logC) 的时间内，一次性将它们全部预处理出来。
  • 空间复杂度： *O(logC)*，即为需要存储的 Y × 2^i 的数量。

submissions-2022090902

参考资料

__END__