9.4如何在大量的数据中找出不重复的整数.py

"""
在2.5亿个整数中找出不重复的整数,注意,内存不足以容纳这2.5亿个整数.
"""

"""
解决思路:
方法一:与前述的题目一样,还是使用hash方法将大文件划分为若干个可以直接读入内存的小文件,然后依次对每个小文件进行分析,
使用字典或set来找到每个小文件中不重复的数字即可.
方法二:位图法:对于本题而言,如果可用的内存空间超过1GB,就可以使用这种方法.具体思路为:假设整数占用4B,4B也就是32位,
可以表示的整数个数为2^32.由于本题只查找不重复的数,而不关心具体数字出现的次数,因此可以分别使用2bit来表示各个数字的状态:
用00表示这个数字没有出现过,01表示出现过1次,10表示出现了多次,11暂不使用.
根据上述的逻辑,在遍历这2.5亿个整数的时候,如果这个整数对应的位图中的位为00,那么修改成01,如果为10则保持不变.这样当所有
数据遍历完成后,可以再遍历一遍位图,位图中为01对应的数字就是没有重复的数字.
"""