题目:给定一个数组，包含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
