Lexi's Leetcode solutions

[phone] 实现一个RandomSet structure,支持insert, remove, random都是O(1)

Posted on: August 29, 2013

想random只能用array,insert remove全O(1)只有hashmap,结合一下就可以了。

public class RandomSetStructure {
  Map<Integer, Integer> map;
  List<Integer> array;
  Random random;
  public void insert(int a) {
    if (map.containsKey(a))
      return;
    array.add(a);
    map.put(a, array.size() - 1);
  }
  public void remove(int a) throws Exception{
    if (!map.containsKey(a))
      throw new RuntimeException();
    int index = map.get(a);
    map.remove(a);
    array.set(index, array.get(array.size() - 1));
    map.put(array.get(index), index);
    array.remove(array.size() - 1);
  }
  public int rand() {
    if (map.isEmpty())
      throw new RuntimeException();
    return array.get(random.nextInt(array.size()));
  }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: