{"id":304,"date":"2017-09-17T08:44:01","date_gmt":"2017-09-17T15:44:01","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=304"},"modified":"2018-07-10T18:27:25","modified_gmt":"2018-07-11T01:27:25","slug":"leetcode-381-insert-delete-getrandom-o1-duplicates-allowed","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-381-insert-delete-getrandom-o1-duplicates-allowed\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 381. Insert Delete GetRandom O(1) &#8211; Duplicates allowed"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 381. Insert Delete GetRandom O(1) - Duplicates allowed - \u5237\u9898\u627e\u5de5\u4f5c EP58\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/mRTgft9sBhA?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p>https:\/\/leetcode.com\/problems\/insert-delete-getrandom-o1-duplicates-allowed\/description\/<\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Design a data structure that supports all following operations in\u00a0<i>average<\/i>\u00a0<b>O(1)<\/b>\u00a0time.<\/p>\n<p><b>Note: Duplicate elements are allowed.<\/b><\/p>\n<ol>\n<li><code>insert(val)<\/code>: Inserts an item val to the collection.<\/li>\n<li><code>remove(val)<\/code>: Removes an item val from the collection if present.<\/li>\n<li><code>getRandom<\/code>: Returns a random element from current collection of elements. The probability of each element being returned is\u00a0<b>linearly related<\/b>\u00a0to the number of same value the collection contains.<\/li>\n<\/ol>\n<p><strong>Idea:<\/strong><\/p>\n<p>Hashtable + array<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-309\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a> <a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-308\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-2-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-2-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><a style=\"font-size: 1rem; color: #0f3647;\" href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-3.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-307\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-3.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-3-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/381-ep58-3-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><strong style=\"font-size: 1rem;\">Solution:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 49 ms\r\nclass RandomizedCollection {\r\npublic:\r\n    \/** Initialize your data structure here. *\/\r\n    RandomizedCollection() {}\r\n    \r\n    \/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. *\/\r\n    bool insert(int val) {        \r\n        m_[val].push_back(vals_.size());\r\n        vals_.emplace_back(val, m_[val].size() - 1);\r\n        return m_[val].size() == 1u;\r\n    }\r\n    \r\n    \/** Removes a value from the collection. Returns true if the collection contained the specified element. *\/\r\n    bool remove(int val) {\r\n        if (!m_.count(val)) return false;\r\n        int index_to_evict = m_[val].back();\r\n        const auto&amp; last_entry = vals_.back();\r\n        \r\n        \/\/ Update index\r\n        m_[last_entry.first][last_entry.second] = index_to_evict;\r\n        \r\n        \/\/ Swap vals\r\n        swap(vals_.back(), vals_[index_to_evict]);\r\n        \r\n        \/\/ Clenup\r\n        vals_.pop_back();        \r\n        m_[val].pop_back();\r\n        if (m_[val].empty()) m_.erase(val);\r\n        \r\n        return true;\r\n    }\r\n    \r\n    \/** Get a random element from the collection. *\/\r\n    int getRandom() {\r\n        return vals_[rand() % vals_.size()].first;\r\n    }\r\nprivate:\r\n    \/\/ val -&gt; indices array: indices in vals_\r\n    unordered_map&lt;int, vector&lt;int&gt;&gt; m_;\r\n    \/\/ {val, index in the indices array}\r\n    vector&lt;pair&lt;int,int&gt;&gt; vals_;\r\n};<\/pre>\n<p>Java<\/p>\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 122 ms (&lt;94.53%)\r\nclass RandomizedCollection {\r\n  class Entry {\r\n    public int value;\r\n    public int index;\r\n    public Entry(int val, int idx) {\r\n      value = val;\r\n      index = idx;\r\n    }\r\n  }\r\n  \r\n  private Map&lt;Integer, List&lt;Integer&gt;&gt; m;\r\n  private List&lt;Entry&gt; vals;\r\n  private Random rand;\r\n\r\n  \/** Initialize your data structure here. *\/\r\n  public RandomizedCollection() {\r\n    m = new HashMap&lt;&gt;();\r\n    vals = new ArrayList&lt;&gt;();\r\n    rand = new Random();\r\n  }\r\n\r\n  \/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. *\/\r\n  public boolean insert(int val) {    \r\n    List&lt;Integer&gt; l = m.getOrDefault(val, new ArrayList&lt;Integer&gt;());\r\n    l.add(vals.size());\r\n    m.put(val, l);\r\n    vals.add(new Entry(val, l.size() - 1));\r\n    return l.size() == 1;\r\n  }\r\n\r\n  \/** Removes a value from the collection. Returns true if the collection contained the specified element. *\/\r\n  public boolean remove(int val) {    \r\n    if (!m.containsKey(val)) return false;\r\n    List&lt;Integer&gt; l = m.get(val);\r\n    int index_to_evict = l.get(l.size() - 1);\r\n    Entry last_entry = vals.get(vals.size() - 1);\r\n\r\n    \/\/ Update index\r\n    m.get(last_entry.value).set(last_entry.index, index_to_evict);\r\n\r\n    \/\/ Swap vals\r\n    vals.set(index_to_evict, last_entry);    \r\n\r\n    \/\/ Cleanup\r\n    vals.remove(vals.size() - 1);\r\n    l.remove(l.size() - 1);\r\n    if (l.size() == 0) m.remove(val);\r\n\r\n    return true;\r\n  }\r\n\r\n  \/** Get a random element from the collection. *\/\r\n  public int getRandom() {    \r\n    return vals.get(rand.nextInt(vals.size())).value;\r\n  }\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Related Problems:<\/strong><\/p>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-380-insert-delete-getrandom-o1\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 380. Insert Delete GetRandom O(1)<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-460-lfu-cache\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 460. LFU Cache O(1)<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-146-lru-cache\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 146. LRU Cache O(1)<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-295-find-median-from-data-stream\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 295. Find Median from Data Stream O(logn) + O(1)<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode.com\/problems\/insert-delete-getrandom-o1-duplicates-allowed\/description\/ Problem: Design a data structure that supports all following operations in\u00a0average\u00a0O(1)\u00a0time. Note: Duplicate elements are allowed. insert(val): Inserts an item val to the collection.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89,70],"tags":[217,92,91],"class_list":["post-304","post","type-post","status-publish","format-standard","hentry","category-data-structure","category-hashtable","tag-hard","tag-o1","tag-random","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/304","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=304"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/304\/revisions"}],"predecessor-version":[{"id":3054,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/304\/revisions\/3054"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=304"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=304"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=304"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}