題目

設(shè)計(jì)一個支持在平均 時間復(fù)雜度 O(1) 下，執(zhí)行以下操作的數(shù)據(jù)結(jié)構(gòu)。

insert(val)：當(dāng)元素 val 不存在時，向集合中插入該項(xiàng)。
remove(val)：元素 val 存在時，從集合中移除該項(xiàng)。
getRandom：隨機(jī)返回現(xiàn)有集合中的一項(xiàng)。每個元素應(yīng)該有相同的概率被返回。
示例 :

// 初始化一個空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合現(xiàn)在包含 [1,2] 。
randomSet.insert(2);

// getRandom 應(yīng)隨機(jī)返回 1 或 2 。
randomSet.getRandom();

// 從集合中移除 1 ，返回 true 。集合現(xiàn)在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的數(shù)字，getRandom 總是返回 2 。
randomSet.getRandom();

思路

哈希表的常用實(shí)現(xiàn)方式有兩種。一種是分離鏈接法(Separate Chaining)。還有一種是線性嗅探法(Linear Probing)。兩種方式的哈希表都可以實(shí)現(xiàn)o(1)時間插入和移除元素。而其中線性嗅探方式實(shí)現(xiàn)的哈希表，由一個一維數(shù)組存儲元素。比較比較方便實(shí)現(xiàn)獲取隨機(jī)元素的功能。

Swift解法

public class LinearProbingHashTable<Key: Hashable, Value> {
    
    private let initCapacity = 4
    
    public fileprivate(set) var count: Int = 0
    
    private var items: [(Key, Value)?]
    
    public init() {
        self.count = 0
        self.items = Array(repeating: nil, count: initCapacity)
    }
    
    private func resize(_ size: Int) {
        count = 0
        let oldItems = items
        items = Array(repeating: nil, count: size)
        for item in oldItems {
            if item != nil {
                put(item!.0, item!.1)
            }
        }
    }
    
    private func hash(_ key: Key) -> Int {
        return key.hashValue & (items.count - 1)
    }
    
    public func put(_ key: Key, _ value: Value) {
        if count * 2 >= items.count {
            resize(2 * items.count)
        }
        var i = hash(key)
        while true {
            if items[i] == nil {
                count += 1
                items[i] = (key, value)
                break
            }
            if items[i]?.0 == key {
                items[i]?.1 = value
                break
            }
            i = (i + 1) & (items.count - 1)
        }
    }
    
    public func get(_ key: Key) -> Value? {
        var i = hash(key)
        while true {
            switch items[i] {
            case .none:
                return nil
            case .some(let item):
                if item.0 == key {
                    return item.1
                } else {
                    i = (i + 1) & (items.count - 1)
                }
            }
        }
    }
    
    public func randomKey() -> Key? {
        while true {
            var i = Int.random(in: 0..<items.count)
            if items[i] != nil {
                return items[i]!.0
            }
        }
        return nil
    }
    
    public func contains(_ key: Key) -> Bool {
        get(key) != nil
    }
    
    public func delete(_ key: Key)  {
        if !contains(key) { return }
        var i = hash(key)
        while key != items[i]?.0 {
            i = (i + 1) & (items.count - 1)
        }
        items[i] = nil
        i = (i + 1) & (items.count - 1)
        while items[i] != nil {
            let newItem = items[i]!
            items[i] = nil
            count -= 1
            put(newItem.0, newItem.1)
            i = (i + 1) & (items.count - 1)
        }
        count -= 1
        if items.count > initCapacity && count <= items.count / 8 {
            resize(items.count >> 1)
        }
    }
    
}
class RandomizedSet {
    let hashTable = LinearProbingHashTable<Int, Bool>()
    /** Initialize your data structure here. */
    init() {
        
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    func insert(_ val: Int) -> Bool {
        if hashTable.contains(val) { return false }
        hashTable.put(val, true)
        return true
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    func remove(_ val: Int) -> Bool {
        if hashTable.contains(val) { 
            hashTable.delete(val)
            return true 
        }
        return false
    }
    
    /** Get a random element from the set. */
    func getRandom() -> Int {
        hashTable.randomKey()!
    }
}