【Leetcode】380. Insert Delete GetRandom O(1)

Description

Design a data structure that supports all following operations in average O(1) time.
1.insert(val): Inserts an item val to the set if not already present.
2.remove(val): Removes an item val from the set if present.
3.getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

Solution

public class RandomizedSet {

    List<Integer> nums;
    HashMap<Integer, Integer> map;
    java.util.Random rand = new java.util.Random();
    public RandomizedSet() {
        nums = new ArrayList<>();
        map = new HashMap<>();
    }

    public boolean insert(int val) {
        if (nums.contains(val)) {
            return false;
        }
        map.put(val, nums.size());
        nums.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!nums.contains(val)) {
            return false;
        }
        if (map.get(val) < nums.size() - 1) {
            //not end, transfer to end
            int lastone = nums.get(nums.size() - 1);
            nums.set(map.get(val), lastone);
            map.put(lastone, map.get(val));
        }
        nums.remove(nums.size() - 1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return nums.get(rand.nextInt(nums.size()));
    }
}

Analyse

以前都不太会做这种题，今天仔细想了一下，还是参考了答案写出来。这种来就类似于在面试的时候给你两个队列来实现栈之类的问题，我记得美团和头条都有问过类似的问题，每次都被恶心到了。这里需要的确实是要把每个函数写的很完整没有一点bug。
开始认为可以只使用nums，因为getRandom和insert都只用nums都可以，但是delete就不行，因为nums的remove有问题，因为题目要求的复杂度是O(1)，你如果不是最后的数字的话，肯定需要遍历list，这样复杂度就不是O(1)了，所以加一个hashmap一点问题都没有。