c**********e
发帖数: 2007 | 1 Given two arrays, each with distinct integers, give an efficient
algorithm to find out the common elements.
显然我们可以对两个数列进行快速排序。但有更简单的算法吗？ |
C***y
发帖数: 2546 | 2 hash
【在 c**********e 的大作中提到】
: Given two arrays, each with distinct integers, give an efficient
: algorithm to find out the common elements.
: 显然我们可以对两个数列进行快速排序。但有更简单的算法吗？
|
P**l
发帖数: 3722 | |
a*****a
发帖数: 46 | 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*H
发帖数: 127 | 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****4
发帖数: 1359 | 6 如果数据没多到内存里放不下hash信息的话，用hashmap就能处理重复
（key, value）扫描A的术后，第一次插入(key, 1)有重复的话，对++value
B扫描，--value，直到0，都是重复的
如果内存放不下hash信息了，只能用mergsort，对2个array进行外部排序
然后从2个array里面取同等大小数据段，扫描，直到任意array空
【在 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.
|
