29. 两数相除
29. 两数相除
题目
Given two integers dividend
and divisor
, divide two integers without using multiplication, division, and mod operator.
The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345
would be truncated to 8
, and -2.7335
would be truncated to -2
.
Return _the quotient after dividing _dividend
bydivisor
.
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]
. For this problem, if the quotient is strictly greater than 2^31 - 1
, then return 2^31 - 1
, and if the quotient is strictly less than -2^31
, then return -2^31
.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.
Constraints:
-2^31 <= dividend, divisor <= 2^31 - 1
divisor != 0
题目大意
给你两个整数,被除数 dividend
和除数 divisor
。将两数相除,要求 不使用 乘法、除法和取余运算。
整数除法应该向零截断,也就是截去(truncate
)其小数部分。例如,8.345
将被截断为 8
,-2.7335
将被截断至 -2
。
返回被除数 dividend
除以除数 divisor
得到的 商 。
**注意:**假设我们的环境只能存储 32 位 有符号整数,其数值范围是 [−2^31, 2^31 − 1]
。本题中,如果商 严格大于 2^31 − 1
,则返回 2^31 − 1
;如果商 严格小于 -2^31
,则返回 -2^31
。
解题思路
处理符号问题:
- 首先判断结果的符号:如果
dividend
和divisor
中只有一个是负数,结果是负的,否则结果为正的。 - 可以通过将
dividend
和divisor
取绝对值来处理后续的无符号整数运算。
- 首先判断结果的符号:如果
倍增法:
- 为了模拟除法,我们可以用减法模拟。直接进行减法会超时,因此采用倍增法提高效率。
- 基本思想是将除数(
divisor
)不断翻倍(即乘以 2),直到超过被除数(dividend
)。这相当于不断减去更大的除数倍数(2 的幂次)来逼近结果。 - 每次当倍增的除数能从被除数中减去时,记录下对应的倍数(即商的部分),直到被除数小于除数为止。
处理边界情况:
- 如果
divisor == 0
,不能除零,直接返回。 - 如果
dividend == -2^31
且divisor == -1
,会导致溢出,这种情况下直接返回2^31 - 1
(即2147483647
)。
- 如果
返回结果:
- 根据之前判断的符号情况,返回商的正负值。
复杂度分析
- 时间复杂度:
O(logn)
,其中 n 是dividend
的大小。每次倍增都将被除数缩小到原来的一半,故时间复杂度为对数级别。 - 空间复杂度:
O(1)
,除了存储变量外,所需的额外空间是常数级的。
代码
/**
* @param {number} dividend
* @param {number} divisor
* @return {number}
*/
var divide = function (dividend, divisor) {
// 处理特殊情况
if (divisor == 0) return Infinity; // 除数为 0
if (dividend == -Math.pow(2, 31) && divisor == -1) return Math.pow(2, 31) - 1; // 溢出情况
// 判断结果符号
let isNegative = dividend > 0 !== divisor > 0;
// 取绝对值,处理负数问题
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
let res = 0;
// 倍增法
while (dividend >= divisor) {
let temp = divisor,
multi = 1;
while (dividend >= 2 * temp) {
temp *= 2; // 除数翻倍
multi *= 2; // 倍数也翻倍
}
dividend -= temp; // 减去翻倍后的除数
res += multi; // 商加上相应的倍数
}
// 返回结果,处理符号
return isNegative ? -res : res;
};