插入、删除和随机查询时间复杂度都为O(1)

解题思路：map+list

import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Random;class RandomizedCollection {    public static void main(String[] args) {        RandomizedCollection s = new RandomizedCollection();        s.insert(1);        s.remove(1);        s.insert(1);        System.out.println(s.list);            }    public Map
     
      
       > map = new HashMap<>();    public List
       
         list = new ArrayList<>();    /** Initialize your data structure here. */    public RandomizedCollection() {            }        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */    public boolean insert(int val) {        list.add(val);        List
        
          temp = map.get(val);        if(temp==null){            temp = new ArrayList<>();            temp.add(list.size()-1);            map.put(val,temp);            return true;        }else{            temp.add(list.size()-1);            return false;        }            }        /** Removes a value from the collection. Returns true if the collection contained the specified element. */    public boolean remove(int val) {        List
         
           temp = map.get(val);        if(temp==null){            return false;        }        int item = temp.remove(0);        if(temp.size()==0) {            map.remove(val);        }        if(list.size()-1==item) {            list.remove(item);        }else {            Integer lastItem = list.remove(list.size()-1);//最后一个元素的内容            list.set(item, lastItem);            //对结尾元素的调整            temp = map.get(lastItem);            temp.remove((Integer)list.size());//这个过程还是比较耗时的            temp.add(item);        }        return true;     }        /** Get a random element from the collection. */    public int getRandom() {        Random random = new Random();        int o = random.nextInt(list.size());        return list.get(o);    }}