算法题：两列找共同元素有O(n)的算法吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

算法题：两列找共同元素有O(n)的算法吗？

算法题：两列找共同元素有O(n)的算法吗？# JobHunting - 待字闺中

c*e2011-06-04 07:06

1 楼

Given two arrays, each with distinct integers, give an efficient
algorithm to find out the common elements.
显然我们可以对两个数列进行快速排序。但有更简单的算法吗？

C*y2011-06-04 07:06

2 楼

hash

【在 c**********e 的大作中提到】

: Given two arrays, each with distinct integers, give an efficient
: algorithm to find out the common elements.
: 显然我们可以对两个数列进行快速排序。但有更简单的算法吗？

P*l2011-06-04 07:06

3 楼

hash

a*a2011-06-04 07:06

4 楼

What if the arrays are huge?
We can use bitset for hash to save space but then what if there are
duplicates in each array?
We can not use one bit to represent a number since it may have duplicates.
What to do?
Thanks.

A*H2011-06-04 07:06

5 楼

of course you can, when you see duplicates in first array, just don't do
anything, when you see dup in second array, it's a common number

【在 a*****a 的大作中提到】

: What if the arrays are huge?
: We can use bitset for hash to save space but then what if there are
: duplicates in each array?
: We can not use one bit to represent a number since it may have duplicates.
: What to do?
: Thanks.

f*42011-06-04 07:06

6 楼

如果数据没多到内存里放不下hash信息的话，用hashmap就能处理重复
（key, value）扫描A的术后，第一次插入(key, 1)有重复的话，对++value
B扫描，--value，直到0，都是重复的
如果内存放不下hash信息了，只能用mergsort，对2个array进行外部排序
然后从2个array里面取同等大小数据段，扫描，直到任意array空

【在 a*****a 的大作中提到】