Problem:
Design a data structure that supports all following operations in average O(1) time.
insert(val)
: Inserts an item val to the set if not already present.remove(val)
: Removes an item val from the set if present.getRandom
: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Idea:
Hashtable + array
Time complexity:
O(1)
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
// Author: Huahua // Running time: 49 ms class RandomizedSet { public: /** Initialize your data structure here. */ RandomizedSet() {} /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ bool insert(int val) { if(m_.count(val)) return false; m_[val] = vals_.size(); vals_.push_back(val); return true; } /** Removes a value from the set. Returns true if the set contained the specified element. */ bool remove(int val) { if(!m_.count(val)) return false; int index = m_[val]; m_[vals_.back()] = index; m_.erase(val); std::swap(vals_[index], vals_.back()); vals_.pop_back(); return true; } /** Get a random element from the set. */ int getRandom() { int index = rand() % vals_.size(); return vals_[index]; } private: // val -> index in the array unordered_map<int, int> m_; vector<int> vals_; }; |
Related Problems:
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment