题目

难度：★★☆☆☆
类型：数学

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

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

说明

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

示例

示例 1
输入: dividend = 10, divisor = 3
输出: 3

示例 2
输入: dividend = 7, divisor = -3
输出: -2

解答

方案1：二分法

由于商不会大于被除数，因此可以把题目当做一个查找问题，就可以使用二分法解决。在程序开始，首先要对结果到的正负号进行判断，并将被除数和输出取绝对值。类似题目【题目69. x的平方根】

构建一个连续递增数组，数组最小值为零，最大值为被除数divident，并取出该数组最中间的元素mid（如果数组有偶数个元素，我们取中点偏左的数字）；
查看mid*divisor，(mid+1)*divisor与被除数的关系，分一下三种情况：
（1）dividend < mid*divisor，表明中点处的元素过大，抛弃数组右半部分；
（2）mid*divisor <= dividend < (mid+1)*divisor，表明中点处的元素即为所求，直接返回；
（3）(mid+1)*divisor <= dividend，表明中点处的元素过小，抛弃数组右半部分；
每次迭代，都要更新数组并取新的中点。

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:

        # 确定结果的正负
        flag = 1 if divisor > 0 and dividend > 0 or divisor < 0 and dividend < 0 else -1

        # 操作数取绝对值
        dividend, divisor = abs(dividend), abs(divisor)

        # 初始化上下边界
        low, upper = 0, dividend

        # 执行循环
        while low <= upper:
            # 二分查找中点
            middle = (low + upper) // 2
            # 情况1，中点*除数>被除数，说明中点处值偏大，抛弃右半部分
            if dividend < middle * divisor:
                upper = middle - 1

            # 情况2，(中点+1)*除数<被除数，说明中点处的值偏小，抛弃左半部分
            elif (middle + 1) * divisor <= dividend:
                low = middle + 1

            # 情况3，中点+1 * 除数 < 被除数 < (中点+1) * 除数，获得商，并限制取值范围
            elif middle * divisor <= dividend < (middle + 1) * divisor:
                return min(max(-2 ** 31, flag * middle), 2 ** 31 - 1)

如有疑问或建议，欢迎评论区留言~

最后编辑于：2019.06.08 17:01:27