面试经典 150 题 （十三）

先来个大的

class RandomizedSet {
    private HashSet<Integer> hashSet;

    public RandomizedSet() {
        hashSet = new HashSet<Integer>();
    }
    
    public boolean insert(int val) {
        if(hashSet.contains(val)){
            return false;
        }
        hashSet.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        return hashSet.remove(val);
    }
    
    public int getRandom() {
        int k=(int)(Math.random()*hashSet.size());
        int i=0;
        for(Integer a: hashSet){
            if(i==k){return a.intValue();}
            i++;
        }
        return 0;
    }
}

笑稀了

变长数组和哈希表组合，变长数组用于存储数组元素，哈希表用于存储元素和下标的键值对，可以O(1)直接找到值的下标

class RandomizedSet {
    //使用变长数组存储元素，使用HashMap存储元素所在数组中的下标
    HashMap<Integer,Integer> mapping;
    List<Integer> list;
    Random random;

    public RandomizedSet() {
        mapping = new HashMap<Integer, Integer>();
        list = new ArrayList<Integer>();
        random = new Random();
    }
    
    public boolean insert(int val) {
        //需要快速判断当前插入元素是否存在
        if(mapping.containsKey(val)){   //mapping.containsKey()时间复杂度是O(1)
            return false;
        }
        list.add(val);
        mapping.put(val,list.size() - 1);
        return true;
    }
    
    public boolean remove(int val) {
        //需要快速判断当前删除元素是否存在
        if(mapping.containsKey(val)){
            int index = mapping.get(val);//获取当前元素在list中的下标

            //将list中的最后一个元素和下标为index的元素交换位置

            mapping.remove(val);//mapping.remove()时间复杂度是O(1)

            list.set(index, list.get(list.size() - 1));
            
            mapping.replace(list.get(index),index);
            list.remove(list.size() - 1);//删除的时间复杂度是O(n),但是删除最后一个元素的时间复杂度是O(1)  
            
            return true;
        }
        return false;
    }
    
    public int getRandom() {
        int randomIndex = random.nextInt(list.size());
        return list.get(randomIndex);
    }
}