题目
Design a data structure that supports all following operations in average O(1) time.
insert(val): Inserts an item val to the set if not already present.remove(val): Removes an item val from the set if present.getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
我自己的答案
public class RandomizedSet { public Set set; /** Initialize your data structure here. */ public RandomizedSet() { set = new HashSet(); } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ public boolean insert(int val) { return set.add(val); } /** Removes a value from the set. Returns true if the set contained the specified element. */ public boolean remove(int val) { return set.remove(val); } /** Get a random element from the set. */ public int getRandom() { int size = set.size(); int randindex = (int)(Math.random()*(size)); Object[] obj = set.toArray(); return (int)obj[randindex]; } } /** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet obj = new RandomizedSet(); * boolean param_1 = obj.insert(val); * boolean param_2 = obj.remove(val); * int param_3 = obj.getRandom(); */好的答案 public class RandomizedSet { // list用于随机访问，map存储数据在list中的索引 ArrayList<Integer> list; HashMap<Integer, Integer> map; int size = 0; /** 初始化. */ public RandomizedSet() { list = new ArrayList<Integer>(); map = new HashMap<Integer, Integer>(); } /** 插入元素，并修改位置map */ public boolean insert(int val) { boolean isContain = map.containsKey(val); if(isContain) return false; else{ list.add(val); map.put(val, size); size++; return true; } } /** 将最后一个元素移动到要删除元素的位置，删除最后一个元素 */ public boolean remove(int val) { boolean isContain = map.containsKey(val); if(isContain){ int index = map.get(val); map.remove(val); if(index < size - 1){ int lastone = list.get(size-1); list.set(index,lastone); map.put(lastone,index); } list.remove(size-1); size--; return true; }else return false; } /** 从list中随机访问元素 */ public int getRandom() { int randnum = (int)(Math.random()*size); return list.get(randnum); } }