Skip to content

Latest commit

 

History

History
6 lines (6 loc) · 661 Bytes

MergeDuplicate.md

File metadata and controls

6 lines (6 loc) · 661 Bytes

两个文件包含无序的数字,数字的大小范围是0-500w左右。如何求两个文件中的重复的数据?

Bit Map

  • 两个文件分别为A和B,采用2-Bitmap(每个数分配2bit,00表示两个文件都不存在,01表示在A出现过,10表示在两个文件中都出现过,11没有意义)进行。
  • 因为800万数据约为2^23次方,所以500万数据共需内存2^23 * 2 bit=1000bit=2MB内存,内存可以接受。
  • 然后扫描扫描两个文件中的整数,查看Bitmap中相对应位,如果是00变01,00变10,10保持不变。
  • 所有数据描完后,查看bitmap,把对应位是10的整数输出即可。