湖南地税局官网站水利建设基金,郴州网签查询,价格网官网,注册新公司名称查询前言
大部分算法默认给定的数据量都比较小#xff0c;只有几个或者几十个元素#xff0c;但是如果将数据量提高到百万甚至几十亿#xff0c;那么处理逻辑就会发生很大差异。在海量数据中#xff0c;普通数据结构都无效了#xff0c;因为内存空间放不下#xff0c;常规的…前言
大部分算法默认给定的数据量都比较小只有几个或者几十个元素但是如果将数据量提高到百万甚至几十亿那么处理逻辑就会发生很大差异。在海量数据中普通数据结构都无效了因为内存空间放不下常规的递归、排序、回溯、贪心和动态规划等思想也无效了执行都会超时。这里介绍三种非常典型的思路
使用位存储其最大的好处是占用的空间是直接存储整数的 1 8 \frac{1}{8} 81例如一个40亿的整数数组如果用整数存储需要16GB左右的空间而如果使用位存储就可以用大约0.5GB的空间大大节省了存储空间。如果文件实在太大无法在内存中放下就需要考虑将大文件分成若干小块先处理每个块最后再逐步得到想要的结果这种方式也叫做外部排序。这样需要遍历全部序列至少两次是典型的用时间换空间的方法。用堆如果在超大数据中找第K大、第K小K个最大、K个最小则特别适合使用堆来做。而且超大数据换成流数据也可以而且几乎是唯一的方式口诀就是“查小用大堆查大用小堆”。
用4KB内存寻找重复元素
题目给定一个数组包含从1到N的整数N最大为32000数组可能还有重复值且N的取值不定若只有4KB的内存可用该如何打印数组中所有重复元素。
分析首先计算所需的位向量大小然后创建一个位向量数组将数组中的元素映射到位向量中的位。在遍历数组时它检查位向量中的相应位是否已经设置如果已设置则表示重复元素将其添加到结果数组中。如果未设置则将相应位设置为1表示已经访问过该元素。最后返回包含重复元素的数组。
代码如下
function findDuplicates(arr) {// 根据最大可能的N值计算所需的位向量大小bit数组大小const maxN 32000;const vectorSize Math.ceil(maxN / 32);// 初始化位向量每个元素都为0const bitVector new Array(vectorSize).fill(0);// 用于存储重复元素的数组const duplicates [];for (const num of arr) {const index Math.floor((num - 1) / 32); // 计算位向量中的索引const bit 1 ((num - 1) % 32); // 计算在索引中的位// 如果该位已经被设置为1说明该元素是重复的if ((bitVector[index] bit) ! 0) {duplicates.push(num);} else {// 否则将该位设置为1表示已经访问过该元素bitVector[index] | bit;}}return duplicates;
}
