LeetCode 380. Insert Delete GetRandom O(1) 题解

import java.util.ArrayList;import java.util.HashMap;import java.util.Random;public class RandomizedSet {		PRivate ArrayList<Integer> arrayList;	private HashMap<Integer, Integer> map;    /** Initialize your data structure here. */    public RandomizedSet() {        arrayList = new ArrayList<Integer>();        map = new HashMap<Integer, Integer>();    }        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */    public boolean insert(int val) {    	// 首先判断待插入的数据是否已经存在    	if(map.containsKey(val)){    		return false;    	}    	// 不存在，插入新元素    	int index = arrayList.size();    	arrayList.add(val);    	map.put(val, index);    	return true;    }        /** Removes a value from the set. Returns true if the set contained the specified element. */    public boolean remove(int val) {        if(map.containsKey(val)){        	int removeIndex = map.get(val);        	// 将该元素在Map所对应的<value,index>键值对删除        	map.remove(val);        	if(!map.isEmpty()){        		// 使用数组的最后一个元素覆盖待删除的元素            	int last = arrayList.get(arrayList.size()-1);            	// 更新（原）最后一个元素在Map中的index值            	map.put(last, removeIndex);            	arrayList.set(removeIndex, last);        	} else {				arrayList.remove(0);			}        	return true;        } else {        	return false;        }    }        /** Get a random element from the set. */    public int getRandom() {    	if(map.isEmpty()){    		return -1;    	}    	Random random = new Random();        int index = random.nextInt(arrayList.size());        return arrayList.get(index);    }}