380/381. Insert Delete GetRandom O(1)

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
思路: 设计个数据结构,用hashmap+List来做。
insert: hashmap中存(val, idx), idx为在List中的元素的下标位置。
remove: 删除的时候要求是O(1);把元素val与List中最后一个元素兑换,然后删除最后一个元素。
1. 从hashmap中拿到元素val在List中的下标 2.拿到List中最后一个元素的值last 3. List中把val下标位置的元素更新为last元素的值,map中加入(last, idx)。 4.最后List中移除最后一个元素,map中remove掉val的key。

public class RandomizedSet {
    List<Integer> list;
    HashMap<Integer, Integer> map;
    Random rand;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        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);
        }
        map.remove(val);
        list.remove(list.size() - 1);
        return true;
    }

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

Follow up: 允许duplicates的存在。

public class RandomizedCollection {
    List<Integer> list;
    HashMap<Integer, Set<Integer>> map;
    Random rand = new Random();

    /** Initialize your data structure here. */
    public RandomizedCollection() {
        list = new ArrayList<>();
        map = new HashMap<>();

    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            Set<Integer> set = map.get(val); // get existing set
            list.add(val); // add to list
            set.add(list.size() - 1); // add idx to set
            map.put(val, set);
            return false;
        } 
        list.add(val);
        int idx = list.size() - 1;
        map.put(val, new HashSet<Integer>(Arrays.asList(idx)));
        return true;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        Set<Integer> set = map.get(val);
        int toRemovePos = set.iterator().next(); // the idx of to remove element 
        set.remove(toRemovePos);
        if (toRemovePos < list.size() - 1) { // list have more than 1 elements
            int last = list.get(list.size() - 1); // get the last element
            list.set(toRemovePos, last); // set the last element at toRemovePos position
            map.get(last).remove(list.size() - 1); // remove the last element from map
            map.get(last).add(toRemovePos); 
        }
        list.remove(list.size() - 1);
        if (map.get(val).isEmpty()) { // check set is empty
            map.remove(val);
        }

        return true;
    }

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

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

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