LeetCode 解题报告 (29)-- 通过加法完成除法

发表于 标签

原题如下：
>Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

题目要求返回一个数除以另外一个数的结果，并且要求不能用乘除或取模，意思就是只能用加减，用加减也不难，先初始化 sum=0，每次 sum 加上除数的大小并与被除数比较，直到 sum 大于等于被除数即可。但是这样的时间复杂度是 Θ(n)，提交时会超时。

解决思路是采用二分搜索，或者说变形的二分搜索。思路类似于上面所说的，但是 sum 每次加上自己的大小，也相当于 sum=sum*2, 这样的时间复杂度是 Θ(log2n), 提交时能够 AC

实现的代码如下：

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
class Solution(object):  
    def divide(self, dividend, divisor):  
        """  
        :type dividend: int  
        :type divisor: int  
        :rtype: int  
        """  
        MAX_INT = pow(2,31)-1  
        if divisor == 0:  
            return MAX_INT

        flag = 1  
        if (dividend > 0 and divisor<0 ) or (dividend<0 and divisor >0):  
            flag = -1  
        a = abs(dividend)  
        b = abs(divisor)  
        res = 0  
        while a >= b :  
            sum = b  
            count =1  
            while a >= sum+sum:  
                sum += sum  
                count += count  
            a-=sum  
            res+=count  
        if res*flag > MAX_INT:  
            return MAX_INT  
        else:  
            return res*flag