題目:給定一個數(shù)組，包含1到N的整數(shù)羡榴，N最大為32000，數(shù)組可能含有重復(fù)的值坑资，且N的取值不定. 若只有4KB內(nèi)存可用耗帕，該如何打印數(shù)組中所有重復(fù)的元素.
限制空間為4KB，最多有8 * 4 * 1024個比特位可以用袱贮，大于32000仿便，可以創(chuàng)建32000個位向量實(shí)現(xiàn).
核心代碼:
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---重復(fù)數(shù)據(jù):\(num)")
} else {
bitSet.set(pos: num0)
}
}
}
測試代碼:
var checkData:[Int] = [1, 2, 24, 800 ,10, 20, 800, 2, 9]
bitManager.checkDuplicates(arr: checkData)
FlyElephant.png
