厦门网站定制,广州网站建设菲利宾,公司网站维护更新流程,建设信用卡中心网站从40亿中产生一个不存在的数
问题描述
给定一个文件#xff0c;包含40亿个非负整数#xff0c;请你设计一个算法#xff0c;产生一个不在该文件中的数字。假设你只有1GB内存。
问题分析
40亿整数,在java中#xff0c;用int存储的话#xff0c;大概需要40亿✖️4B,大约…从40亿中产生一个不存在的数
问题描述
给定一个文件包含40亿个非负整数请你设计一个算法产生一个不在该文件中的数字。假设你只有1GB内存。
问题分析
40亿整数,在java中用int存储的话大概需要40亿✖️4B,大约16G。现在只有1GB很明显是不够的可以考虑位存储可以减少到原空间的1/32大约0.5G,满足题目给定的内存要求
实现思路
使用位存储使用整数对应位置的bit位为1,代表元素存在为0,代表元素不存在。遍历这40亿个数将存在的数对应的bit设置为1。对bit数组再次进行遍历返回为0的第一个下标的对应数字即是40亿中不存在的数。
问题进阶
给定一个文件包含40亿个非负整数请你设计一个算法产生一个不在该文件中的数字。假设你只有10MB内存。
问题分析
只有10MB来存储很明显使用位存储是不够的。位存储需要0.5GB500MB的空间。我们可以采用分块思想。一共需要500MB空间我们只有10MB空间可以分成50个块一般向上取整至2的整数次幂即64个块40亿大概是4G即4*2^ 30,总共2的32次方个数分成64个块每块2^32/64 2 ^26个数我们可以通过两次遍历来找到不存在的数。
实现思路
首先我们申请一个长度为64的整形数组用于统计64个块中元素的个数。遍历这40亿个数判断其属于哪个块可以通过数值大小%64来实现统计结束后找到一个数组元素小于2 ^26的对应块。在申请存储一个块元素所需要的bit空间即2 ^ 26*4B/32 2 ^23B 8MB小于10MB可以实现遍历40亿个数将属于该块的元素对应的bit为设置为1。对bit数组再次进行遍历返回为0的第一个下标的对应数字即是40亿中不存在的数。
20亿个整数中找到出现次数最多的数
问题描述
在20亿个整数中找到出现次数最多的数假设你只有2GB内存。
问题分析
20亿整数大概是2G22^30 2 ^31int类型可以存储不会溢出。可以使map计数键表示数字值表示数字出现的次数这样一个键值对需要8B的存储空间。20亿个数字需要大概2G8B16GB。只有2GB的情况下可以进行分块分为8个块依次进行处理。
实现思路
将20亿个数字映射为8个块可以使用哈希函数(模8)来实现。统计每个块中元素的数量找出最大值比较八个块的最大值找到20亿个数中的最大值返回。
总结
海量数据的处理方法通常只有三种首先是特殊情况让我们寻找海量数据中的最值或者前几个最值可以使用堆来实现之后可以考虑bit位存储整数存储对应下标可以节省到1/32的存储空间如果内存依旧不够可以考虑分块具体的分多少块可以取需要内存和现有内存的比值分块可以采用顺序分块也可以采用哈希分块。
