Leetcode380. 常数时间插入、删除和获取随机元素

题目

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。

insert(val)：当元素 val 不存在时，向集合中插入该项。
remove(val)：元素 val 存在时，从集合中移除该项。
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
示例 :

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

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

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

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

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

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

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

思路

哈希表的常用实现方式有两种。一种是分离链接法(Separate Chaining)。还有一种是线性嗅探法(Linear Probing)。两种方式的哈希表都可以实现o(1)时间插入和移除元素。而其中线性嗅探方式实现的哈希表，由一个一维数组存储元素。比较比较方便实现获取随机元素的功能。

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