12.3

设计 RandomPool结构

设计一种结构,在该结构中有如下三个功能:

• insert(key):将某个key加入到该结构,做到不重复加入。
• delete(key):将原本在结构中的某个key移除。
• getRandom():等概率随机返回结构中的任何一个key。
  要求：Insert、delete 和 getRandom 方法的时间复杂度都是 O(1)。

思路

getRandom()要随机就要知道这个结构中的元素个数，且保证都存在
而删除会导致某个元素消失，这样的话元素不连续，getRandom()会出错
因此本题的考点是删除但是使得元素连续
解决方案是删除时将该删除元素与最后一个元素换位置，删除最后一个元素，这个就会连续
而用O(1)找到元素的方法是hashMap

代码

public static class Pool<K>{
	//为了迅速找到intger，即size
	private HashMap<K, Integer> keyIndexMap;
	//为了迅速找到key
	private HashMap<Integer, K> indexKeyMap;
	int size;
	public Pool() {
		keyIndexMap = new HashMap<K, Integer>();
		indexKeyMap = new HashMap<Integer, K>();
		size = 0;
	}
	
	public void insert(K key){
		
		if(!this.keyIndexMap.containsKey(key)){
			//两个map都要维护
			this.keyIndexMap.put(key, this.size);
			this.indexKeyMap.put(this.size, key);
			//添加个数增加
			this.size++;
		}
	}
	
	public void delete(K key) {
		if(this.keyIndexMap.containsKey(key)){
			//得到删除的index
			int delIndex = keyIndexMap.get(key);
			//将个数减少
			int lastIndex = --size;
			//得到最后的index
			K lastK = indexKeyMap.get(lastIndex);
			//交换位置，并且删除最后一个 
			this.keyIndexMap.remove(key);
			this.keyIndexMap.put(lastK, delIndex);
			this.indexKeyMap.remove(lastIndex);
			this.indexKeyMap.put(lastIndex, lastK);
		}
	}
	
	public K getRandom() {
		if (this.size == 0) {
			return null;
		}
		int rand = (int) (Math.random() * this.size);
		return this.indexKeyMap.get(rand);
	}
}