657. Insert Delete GetRandom O(1)

重点就是O(1),所以用hashmap 加 arraylist 的数据结构。hashmap管O(1)access然后arraylist 管O(1)的删减。失足地方如下

  1. Random到底有多random,如果用了Math.getRandow()%list.size()并没有通过test case。用了import java.util.Random; 然后 rand = new Random(); 然后list.get(rand.nextInt(list.size())); 得到了更棒的随机数。
  2. 在删除的操作中,把list中的最后一个复制到index去,然后删除最后一个元素,同时也不要忘记了在map中要把原来最后一个元素的值对应的value改成index。

int index = map.get(val); 
 int lastone = list.get(list.size()-1);
 
 list.set(index, lastone); 
 map.put(lastone, index);

map.remove(val);
 list.remove(list.size()-1);

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.