Medium
Related Topics: Array / Hash Table / Math / Design / Randomized
LeetCode Source

解題想法

這題又再度驗證 Python 比較好解題，所以用 C++ 可以多鍛鍊實做技巧

基本上這題是實做 insert()、remove()、getRandom()

• insert(): 插入元素，若已有回傳 false，否則插入元素並回傳 true
• remove(): 刪除元素，若已有回傳 true 並刪除元素，否則回傳 false
• getRandom(): 隨機回傳被儲存的一個元素

Python

class RandomizedSet:

    def __init__(self):
        self.bag = []
        
    def insert(self, val: int) -> bool:
        if val in self.bag:
            return False
        else:
            self.bag.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val in self.bag:
            self.bag.remove(val)
            return True
        else:    
            return False

    def getRandom(self) -> int:
        return random.choice(self.bag)

random.choice() 可以隨機回傳元素

C++

class RandomizedSet {
private:
    vector<int> bag;
    unordered_map<int, int> mp;

public:
    RandomizedSet() {

    }
    
    bool insert(int val) {
        if (mp.find(val) != mp.end())
            return false;
        bag.emplace_back(val);
        mp[val] = bag.size() - 1;
        return true;
    }
    
    bool remove(int val) {
        if (mp.find(val) == mp.end())
            return false;
        int last = bag.back();
        mp[last] = mp[val];
        bag[mp[val]] = last;
        bag.pop_back();
        mp.erase(val);
        return true;
    }
    
    int getRandom() {
        return bag[rand() % bag.size()];
    }
};

C++ 的部份我是參考別人的實做方式

vector 是用來儲存值

unordered_map 是用來 map key 跟 value，其中是 mp[val] = key

emplace_back 和 push_back() 功能一樣，但前者效率更嘉

詳細可參考 C++中push_back和emplace_back的区别

其中，remove() 比較需要注意

int last = bag.back();
mp[last] = mp[val]; //change the key(index) of last to old_key(index) of val in m(map)
bag[mp[val]] = last; //change value at index_of_val to 'last' in nums
bag.pop_back();
mp.erase(val);

這系列文被記錄在 Top Interview 150 Series