380. Insert Delete GetRandom O(1) I & II

Design a data structure that supports all following operations in 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.

分析：

因为要求所有操作O(1),插入可以满足这个条件，如果用数组来存储值，getRandom可以满足O(1).但是要求不能重复和delete的时候也满足这个条件，只能使用一个map. key是值，value是位置。

 1 public class RandomizedSet {
 2     ArrayList<Integer> nums;
 3     // value to position
 4     HashMap<Integer, Integer> valueToPositionMap;
 5     Random rand;
 6 
 7     public RandomizedSet() {
 8         nums = new ArrayList<>();
 9         valueToPositionMap = new HashMap<>();
10         rand = new Random(System.currentTimeMillis());
11     }
12     
13     public boolean insert(int val) {
14         if (valueToPositionMap.containsKey(val)) return false;
15         valueToPositionMap.put(val, nums.size());
16         nums.add(val);
17         return true;
18     }
19 
20     public boolean remove(int val) {
21         if (!valueToPositionMap.containsKey(val)) return false;
22         int position = valueToPositionMap.get(val);
23         if (position != nums.size() - 1) {
24             // put the true last one to 'position' in nums
25             int lastOne = nums.get(nums.size() - 1);
26             nums.set(position, lastOne);
27             valueToPositionMap.put(lastOne, position);
28         }
29         valueToPositionMap.remove(val);
30         nums.remove(nums.size() - 1);
31         return true;
32     }
33 
34     public int getRandom() {
35         return nums.get(rand.nextInt(nums.size()));
36     }
37 }

第二种情况：允许有重复数值。

用set来记录同一个值出现的位置，如果被删除的数不是最后一个，则和最后一个换一下位置，然后删除就可以了。

 1 public class RandomizedCollection {
 2     List<Integer> nums;
 3     Map<Integer, Set<Integer>> valueToPositionMap;
 4     Random rand;
 5 
 6     public RandomizedCollection() {
 7         nums = new ArrayList<>();
 8         valueToPositionMap = new HashMap<>();
 9         rand = new Random(System.currentTimeMillis());
10     }
11 
16     public boolean insert(int val) {18         if (!isContained) {
19             valueToPositionMap.put(val, new HashSet<>());
20         }
21         valueToPositionMap.get(val).add(nums.size());
22         nums.add(val);
23         return !isContained;
24     }
25 
26     /**
27      * Removes a value from the collection. Returns true if the collection contained
28      * the specified element.
29      */
30     public boolean remove(int val) {
31         if (!valueToPositionMap.containsKey(val)) {
32             return false;
33         }
34         if (!valueToPositionMap.get(val).contains(nums.size() - 1)) {
35             int currPos = valueToPositionMap.get(val).iterator().next();
36             int lastVal = nums.get(nums.size() - 1);
37             valueToPositionMap.get(lastVal).remove(nums.size() - 1);
38             valueToPositionMap.get(lastVal).add(currPos);
39             valueToPositionMap.get(val).remove(currPos);
40             valueToPositionMap.get(val).add(nums.size() - 1);
41             nums.set(currPos, lastVal);
42         }
43         valueToPositionMap.get(val).remove(nums.size() - 1);
44         if (valueToPositionMap.get(val).isEmpty()) {
45             valueToPositionMap.remove(val);
46         }
47         nums.remove(nums.size() - 1);
48         return true;
49     }
50 
51     /** Get a random element from the collection. */
52     public int getRandom() {
53         return nums.get(rand.nextInt(nums.size()));
54     }
55 }

380. Insert Delete GetRandom O(1) I & II

推荐阅读