[LeetCode刷題筆記] 380 - Insert Delete GetRandom O(1)

題目描述：

Implement the RandomizedSet class:

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.

Follow up: Could you implement the functions of the class with each function works in average O(1) time?

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.

Constraints:

-231 <= val <= 231 - 1
At most 105 calls will be made to insert, remove, and getRandom.
There will be at least one element in the data structure when getRandom is called.

一刷題解（HashSet + List）：

這題需要我們自定義一個插入、刪除、取出隨機元素均為單位時間的數據結構。題目對這個數據結構的幾個方法要求如下：

插入元素：當Set裡沒有該元素時，插入成功並返回true；否則不能插入並返回false。（所有元素都是獨一無二的）
刪除元素：當Set裡沒有該元素時不能刪除，返回false；否則將其刪除並返回true。
提取隨機元素：隨機返回Set裡的一個元素，每個元素的隨機機率相等。

當我看到需要確保插入元素是唯一的時候，就知道HashSet是非常好的選擇，但是光依靠HashSet是不足夠的，因為我們還需要Random取值。我們雖然可以Random一個下標出來，但是HashSet本身是不可以直接通過下標取值的，因此我們還需要一個列表去與HashSet保持同步，然後在隨機下標取值時，就從這個列表中取值。

public class RandomizedSet {

    //增/刪HashSet
    HashSet<int> hash;    
    Random rand;
    //取值列表
    List<int> lis;

    public RandomizedSet()
    {
        hash = new HashSet<int>();
        rand = new Random();
        lis = new List<int>();
    }

    public bool Insert(int val)
    {
        if (hash.Contains(val)) { return false; }
        lis.Add(val);
        hash.Add(val);
        return true;
    }

    public bool Remove(int val)
    {
        if (!hash.Contains(val)) { return false; }
        lis.Remove(val);
        hash.Remove(val);
        return true;
    }

    public int GetRandom()
    {
        return lis[rand.Next(0, lis.Count)];
    }
}

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