第三次电话面试,
a stream data find the number's occurrence more than once.
看到面经这道题,想了个建造一个array 的方法,谁知道要用bitmap, bitmap 是什么鬼,还有就是算空间复杂度的时候的问题。
我的解法:
def sizeN(nums):
if nums is None or len(nums) == 0 or len(nums) == 1:
return None
result = [0]*25000
for elem in nums:
result[elem] += 1
a = []
for i in range(len(result)):
if result[i] > 1:
a.append(i)
return a
print sizeN([1,2,2,3,4,4])
算法的空间复杂度: 对于32 位系统,一个integer 所占空间是4byte,
array 4 *32000
map 4 *32000
all = 8*32000 *0.001 = 200 kb
减少空间负责度:用bit map