讨论/《中级算法》 - 常数时间插入、删除和获取随机元素/
《中级算法》 - 常数时间插入、删除和获取随机元素
共 1 个回复

动态数组+hashmap endpoint指向最后一位数,省了点删除的时间
java提交用时击败99.8
一把辛酸泪,在家里没环境,第一次直接在网页上干出来,

class RandomizedSet {
    private ArrayList<Integer> list;
    private HashMap<Integer,Integer> map;
    private int endPointer;
    private Random random;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        map = new HashMap();
        list = new ArrayList();
        random = 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;
        } else{
            map.put(val,endPointer);
            if(endPointer < list.size()){
                list.set(endPointer,val);
            } else{
                list.add(val);
            }
            ++endPointer;
        }
        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)){
            int index = map.remove(val);
            if(--endPointer != index){
                int tmp = list.get(endPointer);
                list.set(index,tmp);
                map.put(tmp,index);
            }
            return true;
        } else{
            return false;
        }
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        int index= random.nextInt(endPointer);
        return list.get(index);
    }
}
1