本题思路源自Bitmap算法,实际操作可能有一定的限制或难点,仅用于算法思想学习与参考,如有疑问或建议,欢迎留言交流。
定义一个数有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内存即可存放一百亿个数字,符合要求。
读入某个数,就改变该数的对应状态。 若读入的数已存在,则continue
涉及到的思想: