LeetCode--divide-two-integers

xiaoxiao2021-02-28  3

题目描述

Divide two integers without using multiplication, division and mod operator.

思路:一个数除以被除数的本质就是包含多少个被除数.因此我们可以利用乘或位运算将被除数不断变大,直至找到看将被除数放大多少倍可以得到除数.举个栗子:100 / 5 1. 将5乘以2,得到10,而100 > 10,说明100包含更多的5 2.将10乘以2,得到20,100 > 20,因此还可以继续乘 3.将20乘以2,得到40,100 > 40 4.将40乘以2,得到80,100 > 40 5.将80乘以2,得到160,100 < 160 在此之前,我们对除数的放大倍数是以指数方式的,这样可以快速的找到一个其商的一个上界,然后将100-80剩下的作为被除数继续做如上操作. 我们也可以不用指数增长的方式来做,也就是一次增加一个被除数,最终也可以得到结果,但是这种方式的时间复杂度是O(n),而指数增长被除数的时间复杂度是O(log n),其效率相差极大. 还有一个会产生溢出情况的是,当除数是INT_MIN, 而被除数是-1的时候,因为负数的最小值比整数的最大值绝对值大1,因此需要注意这种情况. 代码如下:

class Solution { public: int divide(int dividend, int divisor) { if(dividend==INT_MIN && divisor ==-1) return INT_MAX; if(dividend ==0) return 0; long ans =0, nums1=labs(dividend), nums2=labs(divisor); while(nums2 <= nums1) { int cnt = 1; while((nums2 << cnt) <= nums1) cnt++; ans += (1<<(cnt-1)), nums1 -= (nums2<<(cnt-1)); } return (dividend>0 ^ divisor>0)?-ans:ans; } }; 转自: http://m.blog.csdn.net/qq508618087/article/details/50707159

转载请注明原文地址: https://www.6miu.com/read-1250347.html

最新回复(0)