GuilinDev

Lc0380

05 August 2008

380 Insert Delete GetRandom O(1)

题目

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

1. insert(val)
   

   : Inserts an item val to the set if not already present.

2. remove(val)
   

   : Removes an item val from the set if present.

3. getRandom
   

   : Returns a random element from current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

分析

需要在平均复杂度为 O(1) 实现以下操作：

• insert
• remove
• getRadom

让我们想想如何实现它。先看 insert，有两个平均插入时间为 O(1) 的选择：

• 哈希表：Java 中为 HashMap，Python 中为 dictionary。
• 动态数组：Java 中为 ArrayList，Python 中为 list。

一个个进行思考，虽然哈希表提供常数时间的insert和remove，但是实现 getRandom 时会出现问题。

getRandom 的思想是选择一个随机索引，然后使用该索引返回一个元素。而哈希表中没有线性索引，因此要获得真正的随机值，则要将哈希表中的键转换为列表，这需要线性时间。解决的方法是用一个动态数组存储值，并在该列表中实现常数时间的 getRandom。

动态数组有索引，可以实现常数时间的 insert 和 getRandom，则接下来的问题是如何实现常数时间的 remove。

删除任意索引元素需要线性时间，这里的解决方案是总是删除最后一个元素。

技巧：将要删除元素和最后一个元素交换。 将最后一个元素删除。 为此，必须在常数时间获取到要删除元素的索引，因此需要一个哈希表来存储值到索引的映射。

综上所述，使用以下数据结构：

• 动态数组存储元素值
• 哈希表存储存储值到索引的映射。

代码

class RandomizedSet {
    Map<Integer, Integer> dict;
    List<Integer> list;
    Random rand = new Random();

    /**
     * Initialize your data structure here.
     */
    public RandomizedSet() {
        dict = new HashMap();
        list = new ArrayList();
    }

    /**
     * Inserts a value to the set. Returns true if the set did not already contain the specified element.
     */
    public boolean insert(int val) {
        if (dict.containsKey(val)) { // 重复值，return false
            return false;
        }

        dict.put(val, list.size());
        list.add(list.size(), val);
        return true;
    }

    /**
     * Removes a value from the set. Returns true if the set contained the specified element.
     */
    public boolean remove(int val) {
        if (!dict.containsKey(val)) {
            return false;
        }

        // move the last element to the place idx of the element to delete
        int lastElement = list.get(list.size() - 1);
        int idx = dict.get(val);
        list.set(idx, lastElement);
        dict.put(lastElement, idx);
        
        // delete the last element
        list.remove(list.size() - 1);
        dict.remove(val);
        
        return true;
    }

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

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

This site is open source. Improve this page.