Leetcode 380. O(1) 时间插入、删除和获取随机元素（DAY 157）---- LeetCode 精选 TOP 面试题

ゞ浴缸里的玫瑰 2022-09-09 04:49 60阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷自解） ##

--------------------

class RandomizedSet { 
    public:
        /** Initialize your data structure here. */
        unordered_map<int,int> map;
        vector<int> v;
    
        RandomizedSet() { }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        bool insert(int val) { 
            if(map.find(val) != map.end())  return false;
            v.emplace_back(val);
            map[val] = v.size()-1;
            return true;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) { 
            if(map.find(val) == map.end())  return false;
            swap(v[map[val]],v[v.size()-1]);
            v.pop_back();
            map[v[map[val]]] = map[val];
            map.erase(map.find(val));
            return true;
        }
        
        /** Get a random element from the set. */
        int getRandom() { 
            int pos = rand()%v.size();
            return v[pos];
        }
    };
    
    /** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet* obj = new RandomizedSet(); * bool param_1 = obj->insert(val); * bool param_2 = obj->remove(val); * int param_3 = obj->getRandom(); */

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/ad0c2a58b26c402784200ed09981ec04.png