职业学校查询网站,精准扶贫建设网站的目的,基于html5开发的网站开发,东台市住房和建设局网站关卡名 用4KB内存寻找重复元素 我会了✔️ 内容 1.理解如何用4KB内存寻找重复元素 ✔️ 本关所有题目的重点都是理解如何解决就好#xff0c;面试问的时候能够将问题描述清楚#xff0c;不用写代码。
在海量数据中#xff0c;此时普通的数组、链表、Hash、树等等结构有… 关卡名 用4KB内存寻找重复元素 我会了✔️ 内容 1.理解如何用4KB内存寻找重复元素 ✔️ 本关所有题目的重点都是理解如何解决就好面试问的时候能够将问题描述清楚不用写代码。
在海量数据中此时普通的数组、链表、Hash、树等等结构有无效了 因为内存空间放不下了。而常规的递归、排序回溯、贪心和动态规划等思想也无效了因为执行都会超时必须另外想办法。这类问题该如何下手呢这里介绍三种非常典型的思路 1.使用位存储使用位存储最大的好处是占用的空间是简单存整数的1/8。例如一个40亿的整数数组如果用整数存储需要16GB左右的空间而如果使用位存储就可以用0.5GB的空间这样很多问题就能够解决了。 2.如果文件实在太大 无法在内存中放下则需要考虑将大文件分成若干小块先处理每个块最后再逐步得到想要的结果这种方式也叫做外部排序。这样需要遍历全部序列至少两次是典型的用时间换空间的方法。 3.堆如果在超大数据中找第K大、第K小K个最大、K个最小则特别适合使用堆来做。而且将超大数据换成流数据也可以而且几乎是唯一的方式口诀就是“查小用大堆查大用小堆”。
1. 用4KB内存寻找重复元素
题目要求给定一个数组包含从1到N的整数N最大为32000数组可能还有重复值且N的取值不定若只有4KB的内存可用该如何打印数组中所有重复元素。 分析本身是一道海量数据问题的热身题如果去掉“只有4KB”的要求我们可以先创建一个大小为N的数组然后将这些数据放进来但是整数最大为32000。如果直接采用数组存则应该需要32000*4B128KB的空间而题目有4KB的内存限制我们就必须先解决该如何存放的问题。 如果只有4KB的空间那么只能寻址8*4*2^10个比特这个值比32000要大的因此我们可以创建32000比特的位向量(比特数组)其中一个比特位置就代表一个整数。 利用这个位向量就可以遍历访问整个数组。如果发现数组元素是v那么就将位置为v的设置为1碰到重复元素就输出一下。
public class FindDuplicatesIn32000 {public void checkDuplicates(int[] array) {BitSet bs new BitSet(32000);for (int i 0; i array.length; i) {int num array[i];int num0 num - 1;if (bs.get(num0)) {System.out.println(num);} else {bs.set(num0);}}}class BitSet {int[] bitset;public BitSet(int size) {this.bitset new int[size 5];}boolean get(int pos) {int wordNumber (pos 5);//除以32int bitNumber (pos 0x1F);//除以32return (bitset[wordNumber] (1 bitNumber)) ! 0;}void set(int pos) {int wordNumber (pos 5);//除以32int bitNumber (pos 0x1F);//除以32bitset[wordNumber] | 1 bitNumber;}}
}
