处理海量数据的思路
1.使用位存储：占用的空间是存整数的 1/8 。
2.分块：也叫外部排序，将大文件划分为若干小块，先处理小块再逐步得到想要的结果，需要至少遍历两次全部序列，是用时间换空间的方法。
3.堆：极其适合超大数据或者流数据中找第 K 大，第 K 小， K 个最大， K 个最小等等问题。
用4KB内存寻找重复元素
给定一个数组，长度最大为32000 ，在其中找重复元素，但是只能使用 4KB 内存。
采用位运算。
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);
int bitNumber = (pos & 0x1F);
return (bitSet[wordNumber] & (1 << bitNumber)) != 0;
}
void set(int pos) {
int wordNumber = (pos >> 5);
int bitNumber = (pos & 0x1F);
bitset[wordNumber] |= 1 << bitNumber;
}
}
}
如果对您有帮助，请点赞关注支持我，谢谢！ ❤
如有错误或者不足之处，敬请指正！ ❤
个人主页：星不易 ❤
算法通关村专栏：不易|算法通关村 ❤
