找到重复元素

给定一个数组，包含1到N的整数，N最大为32000，数组可能包含重复的值，且N的取值补丁。若只有4KB的内存，如何打印出数组中所有的重复元素呢？

4KB，481024 bits，比32000要大一些。我们可以创建一个32000bits的位向量，其中每个bit代表一个整数。
利用这个位向量，遍历整个数组，遇到元素v，如果v对应的bit位已经是1，就打印该数字，否则，把对应bit设置为1。

public static void CheckDuplicates(int[] array)
{
    BitSet bs = new BitSet(32000);
    foreach (var num in array)
    {
        var num0 = num - 1; // bs starts at 0, but number starts at 1
        if (bs.Get(num0))
        {
            Console.WriteLine(num);
        }
        else
        {
            bs.Set(num0);
        }
    }
}

class BitSet
{
    private int[] bitSet;

    public BitSet(int size)
    {
        bitSet = new int[size >> 5]; // size / 32
    }

    public bool Get(int pos)
    {
        int wordNumber = pos >> 5; // pos / 32
        int bitNumber = pos & 0x1F; // pos % 32
        return (bitSet[wordNumber] & (1 << bitNumber)) != 0;
    }

    public void Set(int pos)
    {
        int wordNumber = pos >> 5; // pos / 32
        int bitNumber = pos & 0x1F; // pos % 32
        bitSet[wordNumber] |= 1 << bitNumber;
    }
}