用迭代方法实现除法

用迭代方法实现除法

来自 leetcode 的一个题目,题目大概意思是给定两个数计算其商,要求不能用乘法、除法和 mod 运算符来做计算。

该题目在leetcode 打的标签是 Medium(中等难度),而接受率仅有16.6%,题目并不难,但接受率挺低的。

一、暴力法
读完这个题目,最直接的想法就是来个暴力运算了:被除数大于除数时候,不断用被除数减去除数,一直到它小于除数为止,所减的次数,就是商了。

但该算法致命的缺点:慢,当被除数远远大于除数时候,就不得不做大量的循环操作了(比如 123456789 / 2 ,得循环 61728394 次),时间复杂度是O(n)。我试过提交这样的算法,提交运行结果是超时,估计16.6%的接受率之外的提交,包含有很多这种算法了。

二、迭代法
这里定义被除数为 a,除数为 b,为了简化问题,这里假定a 和b 均为非负数(如果存在负数,根据情况取反为正数,算出结果后再做符号变换就可)。a 和 b 的关系不外乎就三种了:a 小于 b;a 在 b 和 2b 之间;a 大于 2b。

对这三种情况分别分析 a / b 的结果:
2.1) a < b 时候,商和余数 分别为:0,a
2.2) b <= a < 2b 时候,商和余数 分别为:1,a – b
2.3) a > 2b 时候,可以考虑先算 a / (2b),假设 计算 a / (2b) 得商 x,余数 y。这里再看 y 的情况,y 和 b 关系 可分为下面两种情况:
2.3.1)如果 y < b, 那么得到,a / b 的商和余数分别为 2x,y 了
2.3.2)如果 y >= b (y是不可能是大于等于 2*b 的),则有 a / b 商和余数 分别为 2x+1, (y-b)了。

总结下 a > 2b 情况,算 a / b 可以先算 a / 2b,令 c = 2b, 也就是算 a / c,而算 a / c 和 算 a / b 没有啥差别的,也是同样的过程,如果a 还大于2c,则先算 a / 2c,令 d = 2c,也就是算 a / d, 继续如果 a 还大于 2d,令 e = 2d ……如此迭代下去。

就算被除数远大于除数,按这个思路,除数两倍两倍的放大,使得运算量会快速减少,从而加快了运算,其时间复杂度为O(logn)。

三、代码实现
Solution.divide 只是做一些边缘条件的判断的,主要实现在 Solution._divide 函数内。 为便于读解,代码去除了原题要求的“-2^31 <= dividend, divisor <= 2^31 – 1” 的约束,题目要求不能用乘法,但没有说不能用左移(<<),就算不能用 左移也没有关系,用 + 来代替代码的<<1 即可。同时,代码的 -n 不是 -1 * n,应该读解为 0 – n:


class Solution:
    '''
    def _divide(self, dividend: int, divisor: int):
        result = 0
        while dividend > divisor:
            dividend -= divisor
            result += 1

        return result, dividend
    '''

    def _divide(self, dividend: int, divisor: int) -> (int,int):
        if dividend < divisor:
            # 被除数小于除数,直接返回就可
            return 0, dividend

        doubleDivisor = divisor << 1
        if divisor <= dividend and dividend < doubleDivisor:
            return 1, dividend - divisor

        result, mod = self._divide(dividend, doubleDivisor)
        result = result << 1

        if mod >= divisor:
            mod -= divisor
            result += 1

        return result, mod

    def divide(self, dividend: int, divisor: int) -> int:
        if divisor == 0:
            return 0

        positive = True
        if dividend < 0:
            dividend = -dividend
            positive = not positive

        if divisor < 0:
            divisor = -divisor
            positive = not positive

        result, mod = self._divide(dividend, divisor)

        if not positive:
            result = -result

        return result

四、最后
提交的结果“Your runtime beats 97.89 % of python3”,看来这样的方法还是不错的。

另外如果计算 x^n,规定不能用库函数,也是可以用类似的算法思想来实现。

(全文完)

(欢迎转载本站文章,但请注明作者和出处 云域 – Yuccn

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注