leetcode381

题目要求

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)的时间内完成对数字的插入，删除和获取随机数的操作，允许插入重复的数字，同时要求每个数字被随机获取的概率和该数字当前在数据结构中的个数成正比。

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

思路和代码

遵循之前基础版本的思路，当解决这种问题的时候我们会用数组和hashmap来做位置的存储，从而更新的时候无需检索。但是在这题的情境下，存在一个问题，举个例子：
假如现在插入1,2,3,3,4,3,3
此时的map中应当是如下：1:[0] 2:[1] 3:[2,3,5,6] 4:[4]
我们先执行删除1，按照之前的规则，我们会删除数组中最后一个元素，并将其值移动到这个位置上map应当被更新为2:[1] 3:[2,3,5,0] 4:[4]
接着我们再删除2，此时虽然最后一个元素还是3，但是这个3在位置数组中的位置却是需要O(n)的时间来查询的，这就违反了O(1)的删除时间复杂度。

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

这里我们采用的方式是继续冗余，即我们在插入每一个元素的时候，同时记录该元素在下标数组中的位置，举个例子：
先插入1，则map的值为[1:[0]]，list的值为[[1,0]] 此处的0代表1这个值在下标数组[0]中位于第0个位置上。
在插入2，则map的值为[1:[0], 2:[1]], list的值为[[1,0],[2,0]]
再插入1，此时map=[1:[0, 2], 2:[1], list的值为[[1,0],[2,0],[1,1]]
此时删除2，同理，我们还是会将数组中最后一个元素的值替换在删除掉元素的位置，此处我们从map中得出2最后一次在数组中出现的下标为1，我们需要将最后位置上的1替换掉当前2的值，之后我们还能从数组中得知，1这个数字它对应的位置下标的索引为2，因此我们再将map[1]中map[1][2]的值替换为2所在的新的位置，即1。此时的map=[1:[0, 1], 2:[] list=[[1,0], [1,1]]

代码如下：

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;
    	}
    }
   
}