[Leetcode][JAVA]第[29]题[两数相除][二分法]

野性酷女 2023-02-19 05:25 25阅读 0赞

#### 【问题描述】\[中等\] ####

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
    
    返回被除数 dividend 除以除数 divisor 得到的商。
    
    整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
    
     
    
    示例 1:
    
    输入: dividend = 10, divisor = 3
    输出: 3
    解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
    示例 2:
    
    输入: dividend = 7, divisor = -3
    输出: -2
    解释: 7/-3 = truncate(-2.33333..) = -2

#### 【解答思路】 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

###### 1. 暴力超时 ######

**时间复杂度：O(N) 空间复杂度：O(1)**

public int divide(int dividend, int divisor) { 
    		if(dividend==Integer.MIN_VALUE&&divisor==-1)
    			return Integer.MAX_VALUE;
    		
    		boolean k=(dividend>0&&divisor>0)||(dividend<0&&divisor<0);
    		int result=0;
    		dividend=-Math.abs(dividend);
                divisor=-Math.abs(divisor);
    		while(dividend<=divisor) { 
    			dividend-=divisor;
    			result+=1;
    		}
    		return k?result:-result;
    	}

###### 2. 二分法优化 ######

![在这里插入图片描述][20200619104923220.png]  
**时间复杂度：O(logN) 空间复杂度：O(1)**

public int divide(int dividend, int divisor) { 
    		if(dividend==Integer.MIN_VALUE&&divisor==-1)
    			return Integer.MAX_VALUE;
    		
    		boolean k=(dividend>0&&divisor>0)||(dividend<0&&divisor<0);
    		int result=0;
    		dividend=-Math.abs(dividend);
                    divisor=-Math.abs(divisor);
    		while(dividend<=divisor) { 
    			int temp=divisor;
    			int c=1;
    			while(dividend-temp<=temp) { 
    				temp=temp<<1;
    				c=c<<1;
    			}
    			dividend-=temp;
    			result+=c;
    		}
    		return k?result:-result;
    	}

#### 【总结】 ####

###### 1.正数统一转化为负数 边界思考量相对较小 ######

###### 2.可用二分法对暴力法进行优化 ######

###### 3.符号问题 脑子要清醒 ######

转载：https://leetcode-cn.com/problems/divide-two-integers/solution/yong-fu-shu-yun-suan-jian-hua-bian-jie-chu-li-by-g/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200619104836262.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200619104923220.png]: https://img-blog.csdnimg.cn/20200619104923220.png