380 & 381. Insert Delete GetRandom O (1)

解法一

思路

insert 和 remove 对于 HashMap 来说都只是 O(1) 的时间复杂度。但 HashMap 是无序的，需要等概率，在 O(1) 取出一个数，那么就必须使用具有索引的 List。而对于 List, 在任意位置的 remve() 需要 O(n) 的时间复杂度，除非这个元素在 List 的末尾。这时，我们就需要将要删除的元素放在末尾，保证 O(1) 时间复杂度。这是本题的关键。所以我们需要 HashMap 和 ArrayList 两种数据结构来实现本题所需要的功能。

代码

class RandomizedSet {
    Random random = new Random();
    LinkedList<Integer> list;
    HashMap<Integer, Integer> map;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new LinkedList<>();
        map = new HashMap<>();
    }

    /** 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)) {
            list.add(val);
            map.put(val, list.size() - 1); // <Key, Value> = <val, index of val in list>
            return true;
        }
        return false;
    }

    /** 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;
        }
        // Move val to the end of the list, and the last element to the position of val
        // Update the position of the last element in HashMap
        // Then remove val
        int loc = map.get(val); // position of val in list
        if (loc < list.size() - 1) { // If val is not the last element
            int last = list.getLast();
            list.set(loc, last); // set last to the position of val
            map.put(last, loc); // update the position of last in HashMap
        }
        map.remove(val);
        list.removeLast();
        return true;
    }

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

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

复杂度分析

O(1)

Follow Up

381. Insert Delete GetRandom O(1) - Duplicates allowed

     思路

     根据题意，既然允许重复元素，那么建立 <元素值, 元素位置> 的 HashMap 时，将多个元素位置用 List 或者 Set 存起来即可。所以映射关系变成了 <Integer, HashSet<Integer>>。
     删除一个元素值时，如果元素值有多个，那么取其中一个进行删除，同样是将 List 中这个元素替换为 List 中最后一个元素，随后删除 List 最后一个元素。要注意的是，还要将最后一个元素的值在 HashMap 中所映射的元素位置集合中的 last index 删除。

代码

class RandomizedCollection {
    Random random = new Random();
    HashMap<Integer, HashSet<Integer>> map; ？？奇怪的是，如果替换成 LinkedList 后面 remove 操作 index 就会 out ot bound. // 后面 Takeaway 有详细的解释
    ArrayList<Integer> list;
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }

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

    /** 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;
        }
        int loc = map.get(val).iterator().next();
        map.get(val).remove(loc);
        int lastIndex = list.size() - 1;
        if (loc < lastIndex) { // This step prevents the overflow ***
            int last = list.get(lastIndex);
            list.set(loc, last);
            // if (map.get(last).size() == 1)
            map.get(last).remove(lastIndex);
            map.get(last).add(loc);
        }
        list.remove(lastIndex);

        // If there is no other val, remove val from the map
        if (map.get(val).isEmpty()) map.remove(val); 
        return true;
    }

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

/**
 * 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();
 */

Takeaway

• List 和 Set 在本题中的区别？为什么不能用 ArrayList 取代 HashSet
  • 对于 List, object.remove(int index), remove 中填写的是所要移除的元素的 index!
  • 对于 ArrayList, object.remove(O object), remove 中填写的是所要移除的元素。
  • 要使 List 的 object.remove() 也是移除指定元素，就得使元素变成 Object。如 int a = 6 => Integer b = new Integer(a)，这样 object.remove(b) 就能删除指定元素了。但在本题中，要求运用 O(1) 的时间复杂度进行任何操作，所以这个 remove 就不适用了。还是得用 HashSet 数据结构。

本作品采用《CC 协议》，转载必须注明作者和本文链接