[LeetCode] 380. Insert Delete GetRandom O(1)

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

解题想法

这题又再度验证 Python 比较好解题，所以用 C++ 可以多锻鍊实做技巧

基本上这题是实做 insert()、remove()、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 numsbag.pop_back();mp.erase(val);

这系列文被记录在 Top Interview 150 Series