算法系列——两数相除(Divide Two Integers)

63 阅读 0 评论 42 点赞

我是靠谱客的博主踏实小海豚，最近开发中收集的这篇文章主要介绍算法系列——两数相除(Divide Two Integers)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

题目链接：https://leetcode-cn.com/problems/divide-two-integers/
Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

解题思路

题目要求我们不使用乘法，除法和取模运算实现两个数的除法。

一种可能的方法，可以利用减法，不断从被减数中减去减数，值到被减数小于等于0,统计减法操作的次数。这种方法的时间复杂度为O(n).我们尝试加速这个过程。对减数b做累加操作，得到2b，4b，8b，16b…2的n次方b.知道大于被减数a 此时的有k个b。然后从 a中减去 k*b.重复上述过程，累加k。最后得到结果。

此时的时间复杂度为O(logn)

程序实现

public class Solution {
    public int divide(int dividend, int divisor) {
        if(divisor==0)
            return Integer.MAX_VALUE;
        boolean negative=(dividend<0&&divisor>0)||(dividend>0&&divisor<0);
        long a=Math.abs((long)dividend);
        long b=Math.abs((long)divisor);
        if(a<b)
            return 0;
        long res=0;
        while(a>=b){
           long count=1;
           long temp=b;
           while(temp+temp<=a){
               temp+=temp;
               count+=count;
           }
           res+=count;
           a-=temp;
        }
        if(negative)
            res=0-res;
        if(res>Integer.MAX_VALUE)
           res=Integer.MAX_VALUE;
        return (int)res;
    }
}