https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/description/
Problem:
Design a data structure that supports all following operations in average O(1) time.
Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.remove(val): Removes an item val from the collection if present.getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
Idea:
Hashtable + array
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 37 38 39 40 41 42 43 44 |
// Author: Huahua // Running time: 49 ms class RandomizedCollection { public: /** Initialize your data structure here. */ RandomizedCollection() {} /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ bool insert(int val) { m_[val].push_back(vals_.size()); vals_.emplace_back(val, m_[val].size() - 1); return m_[val].size() == 1u; } /** Removes a value from the collection. Returns true if the collection contained the specified element. */ bool remove(int val) { if (!m_.count(val)) return false; int index_to_evict = m_[val].back(); const auto& last_entry = vals_.back(); // Update index m_[last_entry.first][last_entry.second] = index_to_evict; // Swap vals swap(vals_.back(), vals_[index_to_evict]); // Clenup vals_.pop_back(); m_[val].pop_back(); if (m_[val].empty()) m_.erase(val); return true; } /** Get a random element from the collection. */ int getRandom() { return vals_[rand() % vals_.size()].first; } private: // val -> indices array: indices in vals_ unordered_map<int, vector<int>> m_; // {val, index in the indices array} vector<pair<int,int>> vals_; }; |
Java
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
// Author: Huahua // Running time: 122 ms (<94.53%) class RandomizedCollection { class Entry { public int value; public int index; public Entry(int val, int idx) { value = val; index = idx; } } private Map<Integer, List<Integer>> m; private List<Entry> vals; private Random rand; /** Initialize your data structure here. */ public RandomizedCollection() { m = new HashMap<>(); vals = new ArrayList<>(); rand = new Random(); } /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ public boolean insert(int val) { List<Integer> l = m.getOrDefault(val, new ArrayList<Integer>()); l.add(vals.size()); m.put(val, l); vals.add(new Entry(val, l.size() - 1)); return l.size() == 1; } /** Removes a value from the collection. Returns true if the collection contained the specified element. */ public boolean remove(int val) { if (!m.containsKey(val)) return false; List<Integer> l = m.get(val); int index_to_evict = l.get(l.size() - 1); Entry last_entry = vals.get(vals.size() - 1); // Update index m.get(last_entry.value).set(last_entry.index, index_to_evict); // Swap vals vals.set(index_to_evict, last_entry); // Cleanup vals.remove(vals.size() - 1); l.remove(l.size() - 1); if (l.size() == 0) m.remove(val); return true; } /** Get a random element from the collection. */ public int getRandom() { return vals.get(rand.nextInt(vals.size())).value; } } |
Related Problems:
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment