Swift-限制空间去重

题目:给定一个数组，包含1到N的整数，N最大为32000，数组可能含有重复的值，且N的取值不定. 若只有4KB内存可用，该如何打印数组中所有重复的元素.

限制空间为4KB，最多有8 * 4 * 1024个比特位可以用，大于32000，可以创建32000个位向量实现.

核心代码:
<pre><code>`class BitSet {

var bitSet:[Int]?

init(size:Int) {
    bitSet = [Int].init(repeating: 0, count: size >> 5) // 除以32
}

func get(pos:Int) -> Bool {
    let num:Int = pos >> 5 // 除以32
    let bitNubmer:Int = pos & 0x1F // 除以32取余
    return (bitSet![num] & (1 << bitNubmer)) != 0
}

func set(pos:Int) {
    let num:Int = pos >> 5 // 除以32
    let bitNumber:Int = pos & 0x1F //除以32取余
    bitSet![num] = bitSet![num] | (1 << bitNumber)
}

}`</code></pre>

<pre><code>` func checkDuplicates(arr:[Int]) {

    let bitSet:BitSet = BitSet(size: 32000)
    
    for i in 0..<arr.count {
        
        let num = arr[i]
        let num0 = num - 1
        
        if bitSet.get(pos: num0) {
            print("FlyElephant---重复数据:\(num)")
        } else {
            bitSet.set(pos: num0)
        }
    }
}`</code></pre>

测试代码:
<pre><code>var checkData:[Int] = [1, 2, 24, 800 ,10, 20, 800, 2, 9] bitManager.checkDuplicates(arr: checkData)</code></pre>

FlyElephant.png