문제

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.

구현 전 예상 풀이

HashSet을 이용해 구현하겠다.
getRandom() 메서드는 Random 객체의 nextInt(set.size()) 메서드를 이용해서 랜덤한 index를 구한 후, set을 이용해서 ArrayList을 만들어서 index에 해당하는 값을 리턴한다.

구현 코드

class RandomizedSet {
    private final HashSet<Integer> set = new HashSet<>();
    private final Random random = new Random();
    public RandomizedSet() {
        
    }
    
    public boolean insert(int val) {
            if (set.contains(val)) {
            return false;
        }

        set.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if (set.contains(val)) {
            set.remove(val);
            return true;
        }

        return false;
    }
    
    public int getRandom() {
        int idx = random.nextInt(set.size());
        ArrayList<Integer> list = new ArrayList<>(set);
        return list.get(idx);
    }
}

380. Insert Delete GetRandom O(1)