leetcode解題：(Medium) 380. Insert Delete GetRandom O(1)

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

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

解題思路：題目時間複雜度要求所有操作都要是平均O(1)，使用HashMap或HashSet的增減、查詢都是O(1)，但隨機取出元素需要用到iterator所以是O(n)，相對的用陣列就能O(1)時間隨機取出元素

因此我們混用2個資料結構，使用HashMap來紀錄數字在陣列中的位置，使用陣列紀錄&隨機取出元素，並且增減時都只在陣列最尾端操作以保證增減元素也是O(1)

程式碼：

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

    public RandomizedSet() {
        set = new ArrayList<>();
        index = new HashMap<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        //val已在set中不用新增，回傳false
        if(index.containsKey(val)) return false;
        
        //val不在set中，把val加到set的最後一格，並將對應的位置存進map中
        index.put(val, set.size());
        set.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        //val不在set中不用刪除，回傳false
        if(!index.containsKey(val)) return false;

        //val在set中，首先從map抓出val的位置
        int loc = index.get(val);
        //如果val的位置不是在set的最後位，找出set最後位的數字並把他移到val的位置
        if(loc < set.size()-1) {
            int lastOne = set.get(set.size()-1);
            index.put(lastOne, loc);
            set.set(loc, lastOne);
        }
        //最後移除set最後位的資料，並從map中移除val的資料
        index.remove(val);
        set.remove(set.size()-1);
        return true;
    }
    
    public int getRandom() {
        return set.get(rand.nextInt(set.size()));
    }
}

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

tags: leetcode medium map/set array