网站建设需注意的问题,爱客crm多少钱,物业管理系统代码,wordpress分类目录描述《算法通关村——位运算在查找重复元素中的妙用》
在海量数据中#xff0c;此时普通的数组、链表、Hash、树等等结构有无效了 #xff0c;因为内存空间放不下了。而常规的递归、排序#xff0c;回溯、贪心和动态规划等思想也无效了#xff0c;因为执行都会超时#xff0c…《算法通关村——位运算在查找重复元素中的妙用》
在海量数据中此时普通的数组、链表、Hash、树等等结构有无效了 因为内存空间放不下了。而常规的递归、排序回溯、贪心和动态规划等思想也无效了因为执行都会超时必须另外想办法。这类问题该如何下手呢这里介绍三种非常典型的思路
使用位存储使用位存储最大的好处是占用的空间是简单存整数的1/8。例如一个40亿的整数数组如果用整数存储需要16GB左右的空间而如果使用位存储就可以用0.5GB的空间这样很多问题就能够解决了。如果文件实在太大 无法在内存中放下则需要考虑将大文件分成若干小块先处理每个块最后再逐步得到想要的结果这种方式也叫做外部排序。这样需要遍历全部序列至少两次是典型的用时间换空间的方法。堆如果在超大数据中找第K大、第K小K个最大、K个最小则特别适合使用堆来做。而且将超大数据换成流数据也可以而且几乎是唯一的方式口诀就是“查小用大堆查大用小堆”。
用 4KB 内存寻找重复元素
分析本身是一道海量数据问题的热身题如果去掉“只有4KB”的要求我们可以先创建一个大小为N的数组然后将这些数据放进来但是整数最大为32000。如果直接采用数组存则应该需要32000*4B128KB的空间而题目有4KB的内存限制我们就必须先解决该如何存放的问题。
如果只有4KB的空间那么只能寻址8*4*2^10个比特这个值比32000要大的因此我们可以创建32000比特的位向量(比特数组)其中一个比特位置就代表一个整数。
利用这个位向量就可以遍历访问整个数组。如果发现数组元素是v那么就将位置为v的设置为1碰到重复元素就输出一下。
package Algorithm15;public class FindRepeatedNum {static class BitSet {private int[] bitSet;BitSet(int size){bitSet new int[size 5];}public int get(int position){int wordNum position 5; // 计算数据在数组中的哪一个位置int bitNum position % 32; // 计算数据在某个位置的那个比特位这两个操作就能够满足把某一个数据进行存在与否的设定。return bitSet[wordNum] (1bitNum);}public void set(int position){int wordNum position 5;int bitNum position % 32;bitSet[wordNum] | (1bitNum);}}public static void findRepeatedNum(int[] nums){BitSet bitSet new BitSet(32000);for(int num :nums){int position num - 1;if(bitSet.get(position) ! 0){System.out.println(num);}else{bitSet.set(position);}}}public static void main(String[] args) {findRepeatedNum(new int[]{1,1,5,6,8,3,23,6,23,8});}
}
