Insert Delete GetRandom O(1)

Leave a comment

November 3, 2016 by oneOokay

两题:一题是不允许duplicates,第二题是允许duplicates.


读第一遍的时候以为考的是如何做到randomize,想着用一个rehashing相关的,但是呢才发现考的是如何达到O(1)的时间复杂度

  • 这个bigOcheatsheet:http://bigocheatsheet.com/
  • Insertion &Deletion Average O(1): Stack, Queue, Singly-Linked List, Doubly-Linked List and HashTable.
  • ArrayList: Insertion & Deletion O(n) 主要是在insert和delete了之后需要移动其他的元素,对于删除最后一个元素的时间复杂度是O(1),所以这题就是考这个。
  • Set的iterator().next()并不是O(1)的复杂度.HashSet/HashMap里头的元素是不维持插入order的.
  • LinkedHashSet可以保持插入元素的order

第一步比较容易想到用Set,因为存在duplication的check.但是set本身是没有get(index)这个功能的,所以并不能实现getRandom().

所以需要一个HashMap和一个ArrayList: HashMap 用来实现查找O(1)(getRandom), 里头存value和在ArrayList里面的index。ArrayList用来存value.

  • insert就直接insert到arraylist的最后一个。
  • Remove的时候要注意的是,把要remove的数和arraylist的最后一个数字交换,然后remove最后一个数字,这样保证了是O(1)而不是O(n).同时要更新map里面交换的值的新的index
  • 这里是一定要一个HashMap来存val和index的,并不能用arraylist.indexOf(),这个时间复杂度是O(N).
  • Random.nextInt(int): 会随机产生一个int,范围是[0,int)

第二题允许duplicates,HashMap<Integer, List>,其他没什么特别的.注意一下ArrayList

  • list.remove(int)的时候,是移除index=int的元素
  • list.remove(Integer.valueOf(int)),是移除list里面值为int的元素

另外Random的那个class要熟悉一下:

Random r = new Random();
r.nextInt(int range)
/** Initialize your data structure here. */
private HashMap<Integer, Integer> map;
private ArrayList list;
private Random rand;
public RandomizedSet() {
map = new HashMap<Integer, Integer>();
list = new ArrayList();
rand = new Random();
}

/** 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;
}
list.add(val);
map.put(val, list.size() - 1);
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)){
return false;
}

int index = map.get(val);
if (index < list.size() - 1) {
int last = list.get(list.size() - 1);
list.set(index, last);
map.put(last, index);
}
list.remove(list.size() - 1);
map.remove(val);
return true;
}

/** Get a random element from the set. */
public int getRandom() {
int r = rand.nextInt(list.size());
return list.get(r);
}
Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: