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

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

核心代码:

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)
    }
    
}

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)
            }
        }
    }

测试代码:

var checkData:[Int] = [1, 2, 24, 800 ,10, 20, 800, 2, 9]
bitManager.checkDuplicates(arr: checkData)

FlyElephant.png