Pocket Gem 面试3

第三次电话面试,

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容