Skip to content

Latest commit

 

History

History

29.Divide-Two-Integers

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

题目不让使用乘除和模运算来计算两数的商。

最简单的想法就是用被除数减除数,直到不能减,这样的时间复杂度是O(n),会超时

那么优化一下的话就是不一直减原除数,而是将除数倍增直到恰好小于等于被除数,然后用被除数减这个数,会节省很多时间。然后对刚才操作的余数可以进行同样的操作。

上面的方法每次都得找一遍这个减数,时间复杂度也挺高。可以再进行优化,第一次找到一个数之后作为一个基数,用被除数减去这个数。然后对原基数向右移一位,用余数去减移位之后的数直到不能减。重复次操作。

用这个方法的时候,每个基数都对应着各自为原除数的倍数c,当被除数或者余数每减去一个基数的时候,商的值应当加上对应的c,这样到最后被除数比除数小的时候过程结束,商的值也就得到了。