leetcode29两数相除

29.两数相除

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        sign = 1 if dividend>0 and divisor>0 or dividend<0 and divisor<0 else -1#结果的符号
        dividend = dividend if dividend > 0 else -dividend
        divisor = divisor if divisor > 0 else -divisor
        #两数转化为正数进行计算
        ans = 0
        while dividend >= divisor:#当被除数大于除数,循环进行
            cur = divisor
            multiple = 1
            while cur + cur < dividend:#找到不大于当前被除数的最大x(x=2的n次方)
                cur += cur#divisor*x,每次乘二
                multiple += multiple#x,每次乘二
            dividend -= cur#找到后减去当前值
            ans += multiple#结果加上当前的最大x
        ans = ans if sign == 1 else -ans
        #处理溢出
        ans = ans if ans <= 2147483647 else 2147483647
        ans = ans if ans >= -2147483648 else 2147483648
        return ans

这个题想了很久,但做出来还是不明白和二分查找的联系在哪里

大佬的解释


@144.0.33 二分查找算法的英文翻译是:binary search algorithm,也可以翻译为二进制搜索,是一种时间复杂度为O(logn)的查找算法,二分查找虽然思想简单,但是应用范围极广(具体可以*上看看),核心思想是每次将有序数组分为一半,则k次操作之后就是原数组的n/2^k个元素,直到这个值变为1,就查找到了那个元素。

对于本题,则是以上思想的逆运算,是从1开始,不断变为二倍的搜索,直到满足要求,因此本题也是考察二分查找思想的运用。

本方法的时间复杂度应该是O(logn * logn),内外while循环都是logn


菜鸡的感悟


对一个算法,不仅要记住,会用,更应该深入地理解这个算法的思想。这道题的对二分查找逆向的思想就很重要。


更加详细的算法及分析请移步leetcode

上一篇:ASP.NET性能优化之分布式Session


下一篇:29. [数学运算]两数相除