题目描述

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

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

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

样例

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示：

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

算法1

二分 + 龟速乘法

• 1、先考虑相除后是正数的情况，$\frac{x}{y} = t$，因此 $x = ty + 余数$ ,即从 $[1,x]$ 中找到满足 $ty <= x$ 集合中最大的 $t$
• 2、通过二分找到满足要求且最大的 t ，判断 ty 是否小于等于 x，可以通过龟速乘法算出 ty 的值
• 3、算出相除后的t后，如果当前整除后是一个负数，则需要将t变成-t
• 4、如果t已经越界则，返回MAX_VAL，否则直接返回

时间复杂度 $loga * logk$

参考文献

参考@胡图图 大佬的解法

Java 代码

class Solution {
    //计算x * b
    static long mul(long a,long k)
    {
        long res = 0;
        while(k > 0)
        {
            if((k & 1) == 1) res += a;
            k >>= 1;
            a += a;
        }
        return res;
    }
    public int divide(int x, int y) {
        List<Long> exp = new ArrayList<Long>();
        long a = x,b = y;
        boolean flag = false;//表示是不是负数
        if (a < 0 && b > 0 || a > 0 && b < 0) flag = true;

        if(a < 0) a = -a;
        if(b < 0) b = -b;

        long l = 0,r = a;
        while(l < r)
        {
            long mid = l + r + 1 >> 1;
            if(mul(mid,b) <= a) l = mid;
            else r = mid - 1;
        }
        long res = l;

        if(flag) res = -res;
        if(res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) res = Integer.MAX_VALUE;

        return (int)res;
    }
}

算法2

贪心
类似二进制的思想

• 1、先考虑相除后是正数的情况，，$\frac{x}{y} = t$，因此 $x = ty + 余数$，将b,2b,4b,8b,....2nb的所有小于a的数值存在exp链表中，且exp链表元素大小从小到大排列
• 2、从exp末端开始枚举，若a >= exp.get(i)，则表示 t 包含1 << i这个数值，将 $2^i$ 加入到res中，并且更新a，a -= exp.get(i)

时间复杂度 $loga$

Java 代码

class Solution {
    public int divide(int x, int y) {
        List<Long> exp = new ArrayList<Long>();
        long a = x,b = y;
        boolean flag = false;//表示是不是负数
        if (a < 0 && b > 0 || a > 0 && b < 0) flag = true;

        if(a < 0) a = -a;
        if(b < 0) b = -b;

        for(long i = b;i <= a;i = i + i)
        {
            exp.add(i);
        }

        long res = 0;
        for(int i = exp.size() - 1;i >= 0;i --)
        {
            if(a >= exp.get(i))
            {
                a -= exp.get(i);
                res += (long)1 << i;
            }
        }

        if(flag) res = -res;
        if(res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) res = Integer.MAX_VALUE;

        return (int)res;
    }
}