算法-对一百亿个正整数进行排序并去重

本题思路源自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内存即可存放一百亿个数字，符合要求。

题解

1. 构造一百亿bit的空间，每个bit设为0。
2. 挨个从文件中读取数字，给对应的bit设为1。
3. 通过bit的状态，对应输出数据。

在这里插入图片描述

在这里插入图片描述

读入某个数，就改变该数的对应状态。 若读入的数已存在，则continue

在这里插入图片描述

在这里插入图片描述

总结

涉及到的思想：

• 利用bit(位)的思想，通过0/1存储数据的状态，不仅仅节省了空间，而且算法非常高效。
  • 假设需要“判断一个数字是否出现多次”，可以通过以下设计来实现：
    • 00：数字不存在
    • 01：数字仅有一个
    • 10：数字出现多次
  • 二进制本身就是组成多姿多彩计算机世界的基础，理论上，直接操纵二进制就可以进行任意运算。
• 利用数组本身的性质“下标”，来实现数据的“间接存储”（实际上并没有保存这个数字，但是却能够操作这个数字）
  • 凡是需要对一定范围内的正整数进行排序去重，都可以使用这个办法（空间换时间）。