整数除法
# 📃 题目描述
题目链接:
- 剑指 Offer II 001. 整数除法 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 29. 两数相除 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定两个整数 a 和 b ,求它们的除法的商 a/b ,要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
注意:
整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231−1]。本题中,如果除法结果溢出,则返回
示例 1:
输入:a = 15, b = 2
输出:7
解释:15/2 = truncate(7.5) = 7
示例 2:
输入:a = 7, b = -3
输出:-2
解释:7/-3 = truncate(-2.33333..) = -2
# 🔔 解题思路
# 暴力
最简单的,不断循环做减法
另外,,int型整数的除法只有一种情况会导致溢出,即
class Solution {
public int divide(int a, int b) {
// 边界条件
if (a == Integer.MIN_VALUE && b == -1) {
return Integer.MAX_VALUE;
}
// 符号
int sign = 1;
if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
sign = -1;
}
int res = 0;
// 全都变成负数做运算,因为最小值的绝对值比最大值的绝对值要大 1
a = (a > 0) ? -a : a;
b = (b > 0) ? -b : b;
while (a <= b) {
a -= b;
res ++;
}
return sign == 1 ? res : -res;
}
}
时间复杂度 O(N)
# 优化
可以将上述解法稍做调整。当被除数大于除数时,继续比较判断被除数是否大于除数的2倍,如果是,则继续判断被除数是否大于除数的4倍、8倍等。如果被除数最多大于除数的 2^k 倍,那么将被除数减去除数的 2^k 倍,然后将剩余的被除数重复前面的步骤
由于每次将除数翻倍,因此优化后的时间复杂度是
下面以 15/2 为例讨论计算的过程
- 15大于2,也大于2的2倍(即4),还大于2的4倍(即8),但小于2的8倍(即16),于是先将 15 减去8(2 的 4 倍),还剩余 7。由于减去的是除数的4倍,减去这部分对应的商是
4
- 接下来对剩余的 7 和除数 2 进行比较,7 大于2,大于2的2倍(即4),但小于2的4倍(即8),于是将 7 减去 4(2的 2 倍),还剩余3。这一次减去的是除数2的2倍,对应的商是
2
- 然后对剩余的 3 和除数 2 进行比较,3 大于2,但小于2的2倍(即4),于是将3减去2,还剩余 1。这一次减去的是除数的 1 倍,对应的商是
1
。 - 最后剩余的数字是1,比除数小,不能再减去除数了。于是 15/2 的商是
4+2+1
,即 7
class Solution {
public int divide(int a, int b) {
// 边界条件
if (a == Integer.MIN_VALUE && b == -1) {
return Integer.MAX_VALUE;
}
// 符号
int sign = 1;
if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
sign = -1;
}
int res = 0;
// 全都变成负数做运算,因为最小值的绝对值比最大值的绝对值要大 1
a = (a > 0) ? -a : a;
b = (b > 0) ? -b : b;
while (a <= b) {
// 除数每次翻倍
int divisor = b;
// 当前除数的倍数
int quotient = 1;
// 代码优化:如果 divisor 已经大于最小值的一半的话,那么退出本次 while 循环
// 因为这个时候 divisor * 2 肯定会小于最小值,超过了题目给的范围
while (divisor > Integer.MIN_VALUE >> 1 && a <= divisor + divisor) {
// 除数翻倍
quotient += quotient;
divisor += divisor;
}
res += quotient;
a -= divisor;
}
return sign == 1 ? res : -res;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10