☆打卡算法☆LeetCode 29、两数相除 算法解析

恬静的小魔龙 发表于 2022/07/29 00:49:26 2022/07/29
【摘要】 推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875 大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定两个整数,进行相除,不能使用乘法、除法和mod运算符。”

题目链接:

来源:力扣(LeetCode)

链接:29. 两数相除 - 力扣(LeetCode) (leetcode-cn.com)

2、题目描述

给定两个整数,被除数 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

  
 
  • 1
  • 2
  • 3
  • 4
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

  
 
  • 1
  • 2
  • 3
  • 4

二、解题

1、思路分析

这个题首先需要考虑整数溢出或边界情况:

当被除数为最小值-232时:

  • 除数为1,可以直接返回答案-232
  • 除数为-1,那么答案为232,产生了溢出,需要返回232-1

当除数为最小值-232时:

  • 除数同样为-232,返回答案1
  • 其他情况,返回0

当除数为0时,返回0。

然后,记被除数和除数为X和Y,结果为Z,使用二分查找法,得到X/Y的最大结果Z,即使得Z x Y ≥ Z成立。

Z x Y的值,可以使用快速乘方法得到。

2、代码实现

代码参考:

public class Solution {
    public int Divide(int dividend, int divisor) {
        // 考虑被除数为最小值的情况
        if (dividend == int.MinValue) {
            if (divisor == 1) {
                return int.MinValue;
            }
            if (divisor == -1) {
                return int.MaxValue;
            }
        }
        // 考虑除数为最小值的情况
        if (divisor == int.MinValue) {
            return dividend == int.MinValue ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (dividend == 0) {
            return 0;
        }
        
        // 一般情况,使用二分查找
        // 将所有的正数取相反数,这样就只需要考虑一种情况
        bool rev = false;
        if (dividend > 0) {
            dividend = -dividend;
            rev = !rev;
        }
        if (divisor > 0) {
            divisor = -divisor;
            rev = !rev;
        }
        
        int left = 1, right = int.MaxValue, ans = 0;
        while (left <= right) {
            // 注意溢出,并且不能使用除法
            int mid = left + ((right - left) >> 1);
            bool check = quickAdd(divisor, mid, dividend);
            if (check) {
                ans = mid;
                // 注意溢出
                if (mid == int.MaxValue) {
                    break;
                }
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return rev ? -ans : ans;
    }

    // 快速乘
    public bool quickAdd(int y, int z, int x) {
        // x 和 y 是负数,z 是正数
        // 需要判断 z * y >= x 是否成立
        int result = 0, add = y;
        while (z != 0) {
            if ((z & 1) != 0) {
                // 需要保证 result + add >= x
                if (result < x - add) {
                    return false;
                }
                result += add;
            }
            if (z != 1) {
                // 需要保证 add + add >= x
                if (add < x - add) {
                    return false;
                }
                add += add;
            }
            // 不能使用除法
            z >>= 1;
        }
        return true;
    }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yS2SVtG4-1658999020983)(https://p6-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/98550cc2f36440619dd710bc71326cbe~tplv-k3u1fbpfcp-watermark.image?)]

3、时间复杂度

时间复杂度 : O(log2 C)

其中 C 表示 32 位整数的范围。二分查找的次数为 O(logC),其中的每一步我们都需要 O(logC) 使用「快速乘」算法判断 Z×Y≥X 是否成立,因此总时间复杂度为 O(log2 C)

空间复杂度: O(1)

只用到常数级的变量。

三、总结

如果我们将被除数和除数的其中(恰好)一个变为了正数,那么在返回答案之前,我们需要对答案也取相反数。

文章来源: itmonon.blog.csdn.net,作者:恬静的小魔龙,版权归原作者所有,如需转载,请联系作者。

原文链接:itmonon.blog.csdn.net/article/details/126039199

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。