Java-LeetCode381. O(1) 时间插入、删除和获取随机元素-HashMap&ArrayList

• 算法
  • 1.ArrayList保存所有元素；Random用于随机获取；HashMap的键是元素，值是键在ArrayList中的位置索引，用LinkedHashSet保存可以以O(1)的时间获取迭代器并删除第一个
  • 2.插入：
    • HashMap中不存在，新建一个LinkedHashSet添加索引；
    • HashMap中存在，直接获取LinkedHashSet并添加索引；
    • 最后将元素添加到ArrayList中；
  • 3.删除：
    • HashMap中不存在，删除失败；
    • HashMap中存在
      • 获得LinkedHashSet中的第一个位置索引并删除之；
      • 随后把ArrayList中的最后一个位置的元素替换这个删除掉的位置的元素（这样后面可以以O(1)的时间删除元素），并将HashMap中对应的元素的位置索引做修改，删除ArrayList最后一个即可；
      • 最后如果删除元素的位置索引空了，需要删除这个键
  • 4.随机获取：使用Random().nextInt(int bound)

class RandomizedCollection {
    ArrayList<Integer> nums;
    HashMap<Integer, Set<Integer>> locations;
    Random random = new Random();
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        nums = new ArrayList<>(10);
        locations = new HashMap<>();
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        boolean contain = locations.containsKey(val);
        if (!contain) {
            locations.put(val, new LinkedHashSet<Integer>());
        }
        locations.get(val).add(nums.size());
        nums.add(val);
        return !contain;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        boolean contain = locations.containsKey(val);
        if (!contain) {
            return false;
        }

        int location = locations.get(val).iterator().next();
        locations.get(val).remove(location);
        if (location < nums.size() - 1) {
            int lastone = nums.get(nums.size() - 1);
            nums.set(location, lastone);
            locations.get(lastone).remove(nums.size()-1);
            locations.get(lastone).add(location);
        }
        nums.remove(nums.size() - 1);
        if (locations.get(val).isEmpty()) {
            locations.remove(val);
        }
        return true;
    }

    /** Get a random element from the collection. */
    public int getRandom() {
        return nums.get(random.nextInt(nums.size()));
    }
}