【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$ 。

思路1

我们知道，乘法可以由多次加法来模拟，那么除法也可以用减法来模拟，例如

20  / 3 = 6.....2
我们可以理解为
20 - 3 = 17 > 3
17 - 3 = 14 > 3
......
5 - 3 = 2 < 3 停止

那么我们可以用这种不断相减的思路，当减去除数，并令记录值count++，得到的值小于除数的时候，停止算法，返回count
代码实现

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
    let res = 0
    let sign_dividend = dividend > 0 ? 1 : -1
    sign_divisor = divisor > 0 ? 1 : -1
    let a = Math.abs(dividend)
    let b = Math.abs(divisor)
    while (a >= b) {
        res++
        a = a - b
    }
    let sign = sign_dividend * sign_divisor
    res =
        sign > 0
            ? Math.min(res, Math.pow(2, 31) - 1)
            : Math.min(res, -Math.pow(-2, 31))
    return res * sign
};

但是这种算法有一个明显的缺点，就是太慢了，假设被除数为 $-2^{31}$ 而除数为 $1$ 的时候，计算的次数非常大，从而会导致算法超时。

思路2

在思路1的基础上，我们可以进行一些优化。但是在优化之前我们还需要注意到，由于javascript定义的Number数据类型边界是 $[-(2^{51}-1), 2^{51}-1]$ ，本来是不需要考虑本题溢出的情况的，但是为了使得逻辑通用，我们依然考虑边界情况，当被除数是 $-2^{31}$ ，除数为 $-1$ 时，得到的值是 $2^{31}$ ，已经溢出了，所以我们可以把被除数和除数都转为负数进行运算，避免溢出。
针对思路1中的运算，我们每次都是减去一个除数，这样试探的效率太低，我们可以思考下面这张试探的思路

20 / 3 = 6......2
等价于
20 - (3 * 1) = 17, k = 1
20 - (3 * 2) = 20 - (3 + 3) = 14, k = 2
20 - (3 * 4) = 20 - (6 + 6) = 8, k =4 
由于8 < 3 * 4，停止，开始令被除数为8
8 - 3 = 5, k = 1
8 - (3 * 2) = 2, k = 2
由于2 < 3 * 2，停止，开始令被除数为2
2 < 3，停止计算，返回结果 res = 4 + 2 = 6

代码实现

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function (a, b) {
    let res = 0
    const MIN = Math.pow(-2, 31),
        MAX = Math.pow(2, 31) - 1
    if (a === MIN && b === -1) return MAX
    let sign = (a > 0) ^ (b > 0) ? -1 : 1
    // 将a和b变为负数
    if (a > 0) a = -a
    if (b > 0) b = -b
    while (a <= b) {
        let value = b
        let k = 1
        while (a <= value + value) {
            value += value
            k += k
        }
        a -= value
        res += k
    }
    return sign === 1 ? res : -res
}

注意到该算法的时间复杂度是 $O((log^n)^2)$ 。

结语

在思路2的基础上其实是可以再优化，使得时间复杂度为 $O(1)$ 的，比如我们可以令 $x$ 从 $2^{31}$ 开始往下试探，当 $x = c$ 时被除数小于除数，下一轮 $x = c - 1$ 继续开始向下试探，这样最多执行31次即可停止，时间复杂度为 $O(1)$

【LeetCode分享】29. 两数相除

题目描述 29. 两数相除

思路1

思路2

结语

推荐阅读更多精彩内容