两数相除
难度:
标签:
题目描述
给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。
整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。
返回被除数 dividend 除以除数 divisor 得到的 商 。
注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231, 231 − 1] 。本题中，如果商 严格大于 231 − 1 ，则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231 。
示例 1:
输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = 3.33333.. ，向零截断后得到 3 。
示例 2:
输入: dividend = 7, divisor = -3 输出: -2 解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。
提示：
-231 <= dividend, divisor <= 231 - 1divisor != 0
代码结果
运行时间: 204 ms, 内存: 14.8 MB
/*
思路：
1. 使用Java Stream API处理这一题不太直接，因为Stream API主要用于处理集合和数组。
2. 因此，在这种情况下，我们仍然使用标准的减法逻辑来解决问题。
*/
public class Solution {
public int divide(int dividend, int divisor) {
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
long dvd = Math.abs((long) dividend);
long dvs = Math.abs((long) divisor);
int result = 0;
while (dvd >= dvs) {
long temp = dvs, multiple = 1;
while (dvd >= (temp << 1)) {
temp <<= 1;
multiple <<= 1;
}
dvd -= temp;
result += multiple;
}
return sign * result;
}
}解释
方法:
这个题解使用二分查找的方法来找出商。首先判断结果的正负号。然后将被除数和除数都转为正数。在二分查找的过程中，使用自定义的 mul 函数来计算中间结果 mid 乘以除数是否小于等于被除数。mul 函数通过位运算来实现乘法，避免使用乘号。最后根据正负号返回二分查找的结果 l，并判断是否溢出。
时间复杂度:
O(log n * log b)
空间复杂度:
O(1)
代码细节讲解
🦆
如何保证二分查找在不使用除法的情况下正确找到商的值，特别是在边界条件下如何处理？
▷🦆
mul函数通过位运算实现乘法时，是否存在特定情况下的效率问题，例如极大或极小的数字乘法？
▷🦆
在二分查找的过程中，你是如何确定将搜索范围从 l 到 r 缩小到恰当的大小，特别是当 mid*divisor 接近 dividend 的时候？
▷🦆
算法在处理可能的溢出时只简单地检查了结果是否超出 32 位整数的范围，是否考虑了在乘法过程中可能的溢出情况？
▷