careercup题目201330928

1000 elements in one bag and 1 million elements in another. how do you find common elements among them. Also give the complexity of your solution.

翻译:1000个元素在一个bag中,另外1000000个元素在另一个bag中,如何找到他们之间相同的元素?同时给出你的解决方案的复杂度。

先解释bag:

袋子和Set类似, 不一样的是: 袋子里面对每个key计数,所以如果同一个key被加入多次那么可以通过接口
获取这个key在这个袋子里面的个数。
 

 i)  HashBag

        内部利用HashMap实现
 

ii) TreeBag

        内部利用TreeMap实现
 
解决方法:
  将1000个元素放入hashtable中,然后迭代1000000个元素的bag找出其中在hashtable中的元素。
  如果内存空间有限,不足以存放1000000个元素,则将集合存到硬盘上,逐块读取,逐块比较。
  
  复杂度:
    时间复杂度:O(m)
    空间复杂度:O(n)
    m代表较大集合的元素数量,n代表较小集合的元素数量
原文地址:https://www.cnblogs.com/caijing/p/3344651.html