leetcode-380-常数时间插入、删除和获取随机元素(Insert Delete GetRandom O(1))-java

题目及测试

package pid381;
/* Insert Delete GetRandom O(1)

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。

    insert(val)：当元素 val 不存在时，向集合中插入该项。
    remove(val)：元素 val 存在时，从集合中移除该项。
    getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例 :

// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();


*/




public class main {
	
	public static void main(String[] args) {
		/*int[][] testTable = {{1,2,3},{2,7,9,3,1},{7,10,4,3,1},{11,6,2,7}};
		for (int[] ito : testTable) {
			test(ito);
		}*/
		test();
	}
		 
	private static void test() {
		RandomizedSet randomSet = new RandomizedSet();
		long begin = System.currentTimeMillis();	    		
		System.out.println(randomSet.insert(1));
		System.out.println(randomSet.insert(1));
		System.out.println(randomSet.insert(2));
		System.out.println(randomSet.getRandom());
		System.out.println(randomSet.remove(1));
		System.out.println(randomSet.remove(1));		
		System.out.println(randomSet.getRandom());		
		long end = System.currentTimeMillis();							
		System.out.println();
		System.out.println("耗时：" + (end - begin) + "ms");
		System.out.println("-------------------");
	}

}

解法1（成功，314ms，超慢）

使用hashset作为结构主体，显然，插入和删除只需要o(1)时间，得到随机数，先将hashset转为数组，再随机选择一个，转为数组可能速度很慢

package pid381;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
class RandomizedSet {

	HashSet<Integer> set;
	
    /** Initialize your data structure here. */
    public RandomizedSet() {
        set=new HashSet<>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {       
    	return set.add(val);
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {        
    	return set.remove(val);
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        Object[] list=set.toArray();
        int length=list.length;        
        int index=(int)(Math.random()*length);
    	return (Integer)list[index];
    }
}

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

解法2（别人的）

这道题让我们在常数时间范围内实现插入删除和获得随机数操作，如果这道题没有常数时间的限制，那么将会是一道非常简单的题，我们直接用一个set就可以搞定所有的操作。但是由于时间的限制，我们无法在常数时间内实现获取随机数，所以只能另辟蹊径。此题的正确解法是利用到了一个一维数组和一个哈希表，其中数组用来保存数字，哈希表用来建立每个数字和其在数组中的位置之间的映射，对于插入操作，我们先看这个数字是否已经在哈希表中存在，如果存在的话直接返回false，不存在的话，我们将其插入到数组的末尾，然后建立数字和其位置的映射。删除操作是比较tricky的，我们还是要先判断其是否在哈希表里，如果没有，直接返回false。由于哈希表的删除是常数时间的，而数组并不是，为了使数组删除也能常数级，我们实际上将要删除的数字和数组的最后一个数字调换个位置，然后修改对应的哈希表中的值，这样我们只需要删除数组的最后一个元素即可，保证了常数时间内的删除。而返回随机数对于数组来说就很简单了，我们只要随机生成一个位置，返回该位置上的数字即可，参见代码如下：

/*
 * 使用Map保存元素和对应的index，这道题要注意，不允许重复元素
 */
public class RandomizedSet
{
    Map<Integer,Integer> map;
    List<Integer> list;
    int size;

    /** Initialize your data structure here. */
    public RandomizedSet()
    {
        map = new HashMap<Integer,Integer>();
        list = new ArrayList<Integer>();
        this.size = 0;
    }

    /** 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;
        else
        {
            list.add(size,val);
            map.put(val,size++);
            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;
        else if(size == 0)
            map.remove(val);
        else
        {
            int tailKey = list.get(size-1);
            map.put(tailKey,map.get(val));
            list.set(map.get(val),tailKey);
            size--;
            map.remove(val);

        }
        return true;
    }

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