# leetcode解題：(Hard) 381. Insert Delete GetRandom O(1) - Duplicates allowed

題目：https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

描述：實作`RandomizedSet`類別，其中的函式要能新增&刪除數字以及隨機回傳一個數字，所有函式的平均時間複雜度需要是`O(1)`，存入的數字能夠重複出現

解題思路：與[380題](https://hackmd.io/@PeterLei/leetcode380)類似但這次需要處理重複元素，所以在HashMap中改用HashSet來儲存多個相同數字的位置，此外邏輯相同

程式碼：

class RandomizedCollection {
    private List<Integer> set;
    private HashMap<Integer, Set<Integer>> index;
    private Random rand;

    public RandomizedCollection() {
        set = new ArrayList<>();
        index = new HashMap<>();
        rand = new Random();
    }
    
    public boolean insert(int val) {
        boolean contain = index.containsKey(val);
        //val不在array中的話，先生成放置位置的hashset
        if(!contain) index.put(val, new HashSet<Integer>());

        //把val加到array的最後一格，並將對應的位置存進對應的hashset中
        index.get(val).add(set.size());
        set.add(val);

        return !contain;
    }
    
    public boolean remove(int val) {
        //val不在array中不用刪除，回傳false
        if(!index.containsKey(val)) return false;

        //val在array中，首先從hashset中找出第一個出現val的位置，並且從hashset中刪除
        int loc = index.get(val).iterator().next();
        index.get(val).remove(loc);

        //如果val的位置不是在array的最後位，找出array最後位的數字並把他移到val的位置
        if(loc < set.size()-1) {
            int lastOne = set.get(set.size()-1);
            index.get(lastOne).remove(set.size()-1);
            index.get(lastOne).add(loc);
            set.set(loc, lastOne);
        }
        //最後移除array最後位的資料
        set.remove(set.size()-1);
        //如果val的hashset沒資料代表array中已經沒有val了，從hashset中移除val的資料
        if(index.get(val).isEmpty()) index.remove(val);
        return true;
    }
    
    public int getRandom() {
        return set.get(rand.nextInt(set.size()));
    }
}

時間複雜度：O(1)
空間複雜度：O(n)

###### tags: `leetcode` `hard` `map/set` `array`