第 15 关| 超大规模数据常见问题：1.青铜挑战——用 4KB 的内存寻找重复元素-灵析社区

在大部分算法中，默认给定的数据量都很小的，例如只有几个或者十几个元素，但是如果将数据量提高到百万甚至十几亿，那处理逻辑就会发生很大差异，这也是算法考查中，经常出现的一类问题。

关卡名	用 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。如果直接采用数组存，则应该需要320004B=128KB的空间，而题目有4KB的内存限制，我们就必须先解决该如何存放的问题。
如果只有4KB的空间，那么只能寻址84*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);//除以32
            int bitNumber = (pos & 0x1F);//除以32
            return (bitset[wordNumber] & (1 << bitNumber)) != 0;
        }

        void set(int pos) {
            int wordNumber = (pos >> 5);//除以32
            int bitNumber = (pos & 0x1F);//除以32
            bitset[wordNumber] |= 1 << bitNumber;
        }
    }
}

#include <stdio.h>
#include <stdlib.h>

typedef struct {
int *bitset;
} BitSet;

BitSet *createBitSet(int size) {
    BitSet *bs = (BitSet *)malloc(sizeof(BitSet));
    bs->bitset = (int *)calloc(size / 32 + 1, sizeof(int));
    return bs;
}

int get(BitSet *bs, int pos) {
    int wordNumber = pos / 32;
    int bitNumber = pos % 32;
    return (bs->bitset[wordNumber] >> bitNumber) & 1;
}

void set(BitSet *bs, int pos) {
    int wordNumber = pos / 32;
    int bitNumber = pos % 32;
    bs->bitset[wordNumber] |= 1 << bitNumber;
}

void checkDuplicates(int *array, int length) {
    BitSet *bs = createBitSet(320000);
    for (int i = 0; i < length; i++) {
        int num = array[i];
        int num0 = num - 1;
        if (get(bs, num0)) {
            printf("%d\n", num);
        } else {
            set(bs, num0);
        }
    }
    free(bs->bitset);
    free(bs);
}

int main() {
    int array[] = {1, 2, 3, 4, 4, 5, 5};
    int length = sizeof(array) / sizeof(int);

    checkDuplicates(array, length);

    return 0;
}

def check_duplicates(array):
    bitset = [0] * (32000 // 32)

    for num in array:
        num0 = num - 1
        if (bitset[num0 // 32] >> (num0 % 32)) & 1:
            print(num)
        else:
            bitset[num0 // 32] |= 1 << (num0 % 32)