算法-对一百亿个正整数进行排序并去重
本题思路源自Bitmap算法，实际操作可能有一定的限制或难点，仅用于算法思想学习与参考，如有疑问或建议，欢迎留言交流。
前置知识
- 一位二进制0/1表示两种世界上任意的两种状态，
- 二位二进制可以表示世界上的任意4种状态，00，01，10，11
- 依此类推，一串二进制数可以表示世界上的任意状态。
题目
定义一个数有2种状态，“不存在这个数”，“存在这个数”，你只有1G出头的运行内存，给出算法设计，对一百亿个数字（数字x∈[0,1010]）进行排序并去重，最后给出所需内存大小（注，直接读取一百亿个数字大概需要37.26G的运行内存）
运存计算所需公式:
1byte=8bit（1字节等于8位）
1024byte=1kb
1024kb=1Mb
分析
在前置知识中，已经提示使用二进制位来表示数的状态，则：
设：“存在这个数”，用1表示，“不存在这个数”，用0表示。
由于一百亿个数字的直接存储已经远远超过普通计算机的运存，不可能放在内存当中，因此只能通过文件读取的形式获得。
数字范围在[0,1010]，构造一百亿bit的空间，每一bit都用于存放数的状态。
构造一百亿bit，需要内存为：
10000000000/8=1250000000 byte
1250000000/1024=1220703.125 kb
1220703.125/1024=1192.09289550781 mb
1192.09289550781/1024=1.16415321826935 gb
只需要1.165G内存即可存放一百亿个数字，符合要求。
题解
- 构造一百亿bit的空间，每个bit设为0。
- 挨个从文件中读取数字，给对应的bit设为1。
- 通过bit的状态，对应输出数据。
读入某个数，就改变该数的对应状态。
若读入的数已存在，则continue
总结
涉及到的思想：
- 利用bit(位)的思想，通过0/1存储数据的状态，不仅仅节省了空间，而且算法非常高效。
- 假设需要“判断一个数字是否出现多次”，可以通过以下设计来实现：
- 00：数字不存在
- 01：数字仅有一个
- 10：数字出现多次
- 二进制本身就是组成多姿多彩计算机世界的基础，理论上，直接操纵二进制就可以进行任意运算。
- 假设需要“判断一个数字是否出现多次”，可以通过以下设计来实现：
- 利用数组本身的性质“下标”，来实现数据的“间接存储”（实际上并没有保存这个数字，但是却能够操作这个数字）
- 凡是需要对一定范围内的正整数进行排序去重，都可以使用这个办法（空间换时间）。
