leetcode381. Insert Delete GetRandom O(1) - Duplicates allowed

题目要求

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

设计一个数据结构，支持能够在O(1)的时间内完成对数字的插入，删除和获取随机数的操作，允许插入重复的数字，同时要求每个数字被随机获取的概率和该数字当前在数据结构中的个数成正比。

强烈建议先看一下这个问题的基础版本，传送门在这里。

思路和代码

网上有一些 java 实现采用OrderSet来解决，这是不合理的。因为有序堆本质上底层是一个最大堆或最小堆，它的插入和删除操作都需要O(lgn)的时间复杂度来完成

代码如下：

public class InsertDeleteGetRandomDuplicatesallowed_381 {
    private List<Pair> list;
    private Map<Integer, List<Integer>> index;
     /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public InsertDeleteGetRandomDuplicatesallowed_381() {
        list = new ArrayList<>();
        index = new HashMap<>();
    }
    public boolean insert(int val) {
        boolean contains = true;
        if(!index.containsKey(val) || index.get(val).isEmpty()) {
            contains = false;
        }
        
        List<Integer> tmp = index.getOrDefault(val, new ArrayList<>());
        tmp.add(list.size());
        index.put(val, tmp);

        list.add(new Pair(val,  tmp.size()-1));
        return !contains;
        
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if(!index.containsKey(val) || index.get(val).isEmpty()) {
            return false;
        }
        List<Integer> tmp = index.get(val);
        int position = tmp.remove(tmp.size()-1);
        if(position != list.size()-1) {
            Pair lastPair = list.get(list.size()-1);
            int lastValue = lastPair.value;            
            List<Integer> lastValuePositions = index.get(lastValue);
            lastValuePositions.set(lastPair.position, position);
            list.set(position, lastPair);
        }
        list.remove(list.size()-1);
        return true;
        
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        int position = (int)Math.floor((Math.random() * list.size()));
        return list.get(position).value;
    }
    
    public static class Pair{
        int value;
        int position;
        
        public Pair(int value, int position) {
            this.value = value;
            this.position = position;
        }
    }
   
}