摘要：題目要求設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，支持能夠在的時(shí)間內(nèi)完成對(duì)數(shù)字的插入，刪除和獲取隨機(jī)數(shù)的操作，允許插入重復(fù)的數(shù)字，同時(shí)要求每個(gè)數(shù)字被隨機(jī)獲取的概率和該數(shù)字當(dāng)前在數(shù)據(jù)結(jié)構(gòu)中的個(gè)數(shù)成正比。網(wǎng)上有一些實(shí)現(xiàn)采用來(lái)解決，這是不合理的。此時(shí)的代碼如下

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();

設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，支持能夠在O(1)的時(shí)間內(nèi)完成對(duì)數(shù)字的插入，刪除和獲取隨機(jī)數(shù)的操作，允許插入重復(fù)的數(shù)字，同時(shí)要求每個(gè)數(shù)字被隨機(jī)獲取的概率和該數(shù)字當(dāng)前在數(shù)據(jù)結(jié)構(gòu)中的個(gè)數(shù)成正比。

強(qiáng)烈建議先看一下這個(gè)問(wèn)題的基礎(chǔ)版本，傳送門(mén)在這里。

遵循之前基礎(chǔ)版本的思路，當(dāng)解決這種問(wèn)題的時(shí)候我們會(huì)用數(shù)組和hashmap來(lái)做位置的存儲(chǔ)，從而更新的時(shí)候無(wú)需檢索。但是在這題的情境下，存在一個(gè)問(wèn)題，舉個(gè)例子：
假如現(xiàn)在插入1,2,3,3,4,3,3
此時(shí)的map中應(yīng)當(dāng)是如下：1:[0] 2:[1] 3:[2,3,5,6] 4:[4]
我們先執(zhí)行刪除1，按照之前的規(guī)則，我們會(huì)刪除數(shù)組中最后一個(gè)元素，并將其值移動(dòng)到這個(gè)位置上map應(yīng)當(dāng)被更新為2:[1] 3:[2,3,5,0] 4:[4]
接著我們?cè)賱h除2，此時(shí)雖然最后一個(gè)元素還是3，但是這個(gè)3在位置數(shù)組中的位置卻是需要O(n)的時(shí)間來(lái)查詢的，這就違反了O(1)的刪除時(shí)間復(fù)雜度。

網(wǎng)上有一些java實(shí)現(xiàn)采用OrderSet來(lái)解決，這是不合理的。因?yàn)橛行蚨驯举|(zhì)上底層是一個(gè)最大堆或最小堆，它的插入和刪除操作都需要O(lgn)的時(shí)間復(fù)雜度來(lái)完成

這里我們采用的方式是繼續(xù)冗余，即我們?cè)诓迦朊恳粋€(gè)元素的時(shí)候，同時(shí)記錄該元素在下標(biāo)數(shù)組中的位置，舉個(gè)例子：
先插入1，則map的值為[1:[0]]，list的值為[[1,0]] 此處的0代表1這個(gè)值在下標(biāo)數(shù)組[0]中位于第0個(gè)位置上。
在插入2，則map的值為[1:[0], 2:[1]], list的值為[[1,0],[2,0]]
再插入1，此時(shí)map=[1:[0, 2], 2:[1], list的值為[[1,0],[2,0],[1,1]]
此時(shí)刪除2，同理，我們還是會(huì)將數(shù)組中最后一個(gè)元素的值替換在刪除掉元素的位置，此處我們從map中得出2最后一次在數(shù)組中出現(xiàn)的下標(biāo)為1，我們需要將最后位置上的1替換掉當(dāng)前2的值，之后我們還能從數(shù)組中得知，1這個(gè)數(shù)字它對(duì)應(yīng)的位置下標(biāo)的索引為2，因此我們?cè)賹?b>map[1]中map[1][2]的值替換為2所在的新的位置，即1。此時(shí)的map=[1:[0, 1], 2:[] list=[[1,0], [1,1]]

代碼如下：

public class InsertDeleteGetRandomDuplicatesallowed_381 {
    private List list;
    private Map> 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 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 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 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;
        }
    }
   
}