380. Insert Delete GetRandom O(1) - Medium

前往題目

想法

經過這麼多演算法的洗禮還有自修的演算法課程，總算沒讓自己失望:D以下是分析

1. 如果使用array，insert和remove都需要index，但是傳入的值是value，每次都要花時間搜尋。如果使用Map來儲存映射關係那還要處理array擴增的問題，所以不選這個
2. 如果用LinkedList，insert可以O(1)，但是remove和getRandom都要O(n)，也不方便；就算是double LinkedList也沒用，都沒辦法瞬間定位到value的地方
3. 如果使用HashMap，雖然insert和remove都是O(1)時間，但getRandom就沒有這麼方便了，最差需要O(n)，因為HashMap沒有index，這方面可以用ArrayList來補足，一方面解決了array擴增的問題，還能提供insert以及remove的O(1)甚至getRandom的時候也可以直接用隨機數在O(1)的時間找到該隨機index的值並回傳

思路

差了一點點，remove那邊原來是需要補足空位的，不然arraylist擴充或縮減的時候會打亂index。和尾巴調換就可以完美又簡單的解決這個問題

1. 使用hashmap和arraylist，hashmap儲存value和index的映射關係，arraylist儲存所有數值方便快速存取
2. insert只要簡單的放到arraylist最後面，map更新一下映射就可以
3. remove需要特別注意不能有空位，所以把要remove的那位先跟尾巴調換，再進行移除
4. getRandom非常簡單，用java自帶的Random()，範圍就是arraylist的size，才不會出界

Code

class RandomizedSet {
    private List<Integer> valList;
    // <value, index> mapping
    private Map<Integer, Integer> map;
    Random random;

    public RandomizedSet() {
        this.valList = new ArrayList();
        this.map = new HashMap();
        this.random = new Random();
    }
    
    public boolean insert(int val) {
        // Check present
        if (isPresent(val)) return false;

        valList.add(val);
        map.put(val, valList.size() - 1);
        return true;
    }
    
    public boolean remove(int val) {
        // Check absence
        if (!isPresent(val)) return false;

        // index of the value
        int index = map.get(val);
        int lastIndex = valList.size() - 1;

        // When removing non-tail element
        // Swap target value and the tail
        if (index != lastIndex) {
            int lastVal = valList.get(lastIndex);
            valList.set(index, lastVal);
            map.put(lastVal, index);
        }
        
        // Remove from list and map
        // val has been swapped to the end
        valList.remove(lastIndex);
        map.remove(val);

        return true;
    }
    
    public int getRandom() {
        // guaranteed that at least one element exists when this method is called

        if (valList.size() == 1) return valList.get(0);

        // Obtain random number
        return valList.get(random.nextInt(valList.size()));
    }

    private boolean isPresent(int val) {
        return map.containsKey(val);
    }
}

2024/05/08

• 簡單，不過remove錯了😭