###### tags: `Leetcode` `medium` `design` `hash` `python` `c++`

# 380. Insert Delete GetRandom O(1)

## [題目連結:] https://leetcode.com/problems/insert-delete-getrandom-o1/

## 題目:
Implement the ```RandomizedSet``` class:

* ```RandomizedSet()``` Initializes the RandomizedSet object.
* ```bool insert(int val)``` Inserts an item ```val``` into the set if not present. Returns true if the item was not present, ```false``` otherwise.
* ```bool remove(int val)``` Removes an item ```val``` from the set if present. Returns ```true``` if the item was present, ```false``` otherwise.
* ```int getRandom()``` Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the **same probability** of being returned.

You must implement the functions of the class such that each function works in **average** ```O(1)``` time complexity.

* There will be at least one element in the data structure when getRandom is called.

**Example 1:**

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

## 解題想法:
* 此題為，實作一個資料結構，能夠加入元素(insert)、刪除元素(remove)以及可以從元素裡面隨機挑選一個元素出來(getRandom)，並且所有操作都必須要在 O(1) 的時間完成。

* 分析: time
* insert:
* list: O(1)
* dict: O(1)
* remove:
* list: O(n)
* **dict: O(1)**
* getRandom:
* **list: O(1)**
* dict: O(n)
* 實作要點:
* init: 初始定義
* self.list
* self.dict
* bool insert(val):
* 同時將val加入於self.list、self.dict中
* 用self.dict找是否有出現重複:O(1)
* 對於self.dict
* key為val
* self.dict[key]為在self.list中的位置
* bool remove(val):
* 對於上述分析:
* 用list:O(n)
* 用dict:O(1)
* **所以先交換list內容於list[-1]**
* **再刪除list[-1]這樣才O(1)**
* 作法:
* **Step1**:先紀錄self.list[-1]的元素
* last_val=self.list[-1]
* **Step2**:紀錄要刪除的val於self.dict之中，所存的pos
* cur_pos=self.dict[val]
* **Step3**: 將list[-1]的值移到list[cur_pos]
* **Step4**: 將dict[last]的內容改成cur_pos
* **Step5**:
* 刪除self.dict[val]
* 刪除self.list[-1]

* int getRandom:
* 用list: O(1)
* 用dict: O(n)
* 所以直接random.choice(self.list)即可 (for python : import random)

## Python:

import random
class RandomizedSet(object):

    def __init__(self):
        self.list=[]
        self.dict={}

    def insert(self, val):
        """
        :type val: int
        :rtype: bool
        """
        #用dict找是否有出現重複:O(1)
        if val in self.dict:
            return False
        self.dict[val]=len(self.list) #key為val dict[key]為list中所在位置
        self.list.append(val)
        return True

    def remove(self, val):
        """
        :type val: int
        :rtype: bool
        """
        #用list:O(n) 用dict:O(1)
        #所以交換list內容於list[-1] 
        #刪除list[-1]這樣才O(1)
        if val not in self.dict:
            return False
        last_val=self.list[-1]
        cur_pos=self.dict[val]
        #將list[-1]的值移到list[cur_pos]
        self.list[cur_pos]=last_val
        #將dict[last]的內容改成cur_pos
        self.dict[last_val]=cur_pos
        del self.dict[val]
        del self.list[-1]
        return True

    def getRandom(self):
        """
        :rtype: int
        """
        #用list:O(1) 用dict:O(n)
        return random.choice(self.list)


result = RandomizedSet()
r1 = result.insert(1)
r2 = result.remove(2)
r3 = result.insert(2)
r4 = result.getRandom()
r5 = result.remove(1)
r6 = result.insert(2)
r7 = result.getRandom()
print(r1,r2,r3,r4,r5,r6,r7)

## C++:
* unordered_map:
* 刪除key用 **.erase(key)**
* return隨機數
* 數組[ **rand()** % 數組.size() ]

class RandomizedSet {
public:
    RandomizedSet() {
        
    }
    //list、dict:O(1)
    bool insert(int val) {
        if (dict.find(val)!=dict.end()) //same as dict.count(val)
            return false;
        dict[val]=list.size();
        list.push_back(val);
        return true;
    }
    //dict:O(1)
    bool remove(int val) {
        if (!dict.count(val))
            return false;
        int last_val=list.back();
        int cur_pos=dict[val];
        list[cur_pos]=last_val;
        dict[last_val]=cur_pos;
        //delete val info in dict、list
        list.pop_back(); //pop last item
        dict.erase(val);
        return true;
    }
    
    int getRandom() {
        return list[rand() % list.size()];
    }
private:
    vector<int> list;
    unordered_map<int,int> dict;
};

/**
 * 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();
 */