Leetcode:Divide Two Integers分析和实现

题目要求我们用一个32位整数整除另外一个整数，但是不允许我们使用除法，乘法和取模运算。

有趣的问题，下面说一下我的思路：

首先，先给出两个正整数除法运算的过程。假设a为被除数，而b为除数。在计算机中无符号整数除法div可以用下面的数学公式来表示：

即计算机除法中的a/b实际上是数学意义上a/b代表的有理数向下取整值。可以换一个方法来等价表示上面公式：

因此我们只需要能找到一个值c，满足下面条件即可：

但是我们不能从1到正无穷枚举c，因为如果a足够大且b足够小，那么c的值可能要上亿，上亿次的枚举消耗的时间非常可怕。但是我们不能使用乘法又该如何快速增大枚举值呢。这源于一个思路，v[0]=1,v[1]=v[0]+v[0],...,v[n]=v[n-1]+v[n-1]。发现了吗，v[i]=2^i，而32位整数绝对不会超过v[32]，因此我们可以快速的利用v数组快速逼近c。

实际做法如下：

v and u are arrays with size 32

v[0] = 1, u[0] = b

limit = 0

for(; u[limit] < a; limit = limit + 1)

　　u[limit + 1] = u[limit ] + u[limit ]

　　v[limit + 1] = v[limit] + v[limit]

这样我们就得到一个数组u，并且保证了u[0], ..., u[limit - 1] < a，且u[limit] >= a，实际上u[i] = b * 2^i。但是我们又该如何能够借助这样一个数组u计算出最终的c？

由于每个整数在计算机中都是由二进制表示而成，因此c必然等于2^i1+2^i2+...+2^in，其中i1,...in互不相同并按增序排序。因此我们所要找的实际上是这样一组i1,i2,...,in。由于2^n=1+2^0+2^1+2^2+...+2^(n-1)，因此我们能得知2^in>2^i1+2^i2+...+2^i_n-1,换句话说有2^in<=c<2^(in+1)，等价的形式为u[in]=b*2^in<=b*c=a<b*2^(in+1)=u[in+1]。到了这一步我们就知道如何快速地决定in，而对于i_n-1的计算，可以通过u[i_n-1]=b*2^i_n-1<=b*(c-2^in)=a-u[in]<b*2^(i_n-1+1)=u[i_n-1+1]得出，推理过程如上。这样不断地计算下去，我们就可以将i1,i2,...,in全部计算出来。

用代码展示上面的结论：

r = a, c = 0

for(i = limit; r >= b; i--)

　　if(u[i] <= r)

　　　　r = r - u[i]

　　　　c = c + v[i]

综合上面我们已经得到了计算两个正整数的方式。上面这个算法的时间复杂度与空间复杂度均为常数O(1)，因为不存在与输入相关联的冗余循环。

对于a，b均为负数的除法，有a/b=(-a)/(-b)，因此可以直接用上述正整数除法的运算方式。对于a为负数的运算。计算机中对于带一个负数除法ndiv的定义如下：

但是我们不希望为带负数的重新定义一个新的算法，故我们要使用下面公式提供的计算c的方法：

故到了这里问题全面解决。当然这只是理论上的，实践上还会存在数值超出32位整数表示范围的情况，这需要读者自己对特殊情况进行处理。

最后提供一下AC代码，主要是需要对Integer.MIN_VALUE和越界做处理：

 package cn.dalt.leetcode;

 /**
  * Created by dalt on 2017/6/21.
  */
 public class DivideTwoIntegers {
     public int divide(int dividend, int divisor) {
         if (divisor == 0) {
             throw new ArithmeticException();
         }
         if (divisor == Integer.MIN_VALUE) {
             return dividend == Integer.MIN_VALUE ? 1 : 0;
         }
         if (dividend == Integer.MIN_VALUE) {
             if (divisor == -1) {
                 return Integer.MAX_VALUE;
             }
             if (divisor == 1) {
                 return Integer.MIN_VALUE;
             }
             if (divisor < 0) {
                 return divide(dividend - divisor, divisor) + 1;
             }
             return divide(dividend + divisor, divisor) - 1;
         }
         if (divisor < 0) {
             return divide(-dividend, -divisor);
         }
         if (dividend < 0) {
             return -divide(-dividend, divisor);
         }
         return div(dividend, divisor);
     }

     /**
      * Calculate floor(a/b)
      *
      * @param a a positive number
      * @param b a positive number
      * @return floor(a/b)
      */
     public int div(int a, int b) {
         int[] v = new int[32];
         int[] u = new int[32];
         v[0] = 1;
         u[0] = b;
         int limit = 0;
         for (; u[limit] <= a && u[limit] > 0; limit++) {
             u[limit + 1] = u[limit] + u[limit];
             v[limit + 1] = v[limit] + v[limit];
         }
         int c = 0;
         int r = a;
         for (limit--; r >= b; limit--) {
             if (r >= u[limit]) {
                 c += v[limit];
                 r -= u[limit];
             }
         }
         return c;
     }
 }

巴特西

Leetcode:Divide Two Integers分析和实现

最新文章

热门文章