380. 常数时间插入、删除和获取随机元素

原创
2020/12/26 20:44
阅读数 39

题目描述

解题思路

  1. 我们具有两个平均插入时间为O(1) 的选择,哈希表和数组。

  2. 虽然哈希表提供常数时间的插入和删除,但是实现 getRandom 时会出现问题。哈希表中没有索引,因此要获得真正的随机值,则要将哈希表中的键转换为列表,这需要线性时间,解决的方法是用一个列表存储值,并在该列表中实现常数时间的 getRandom。

  3. 列表有索引可以实现常数时间的 insert 和 getRandom,则接下来的问题是如何实现常数时间的 remove。可以采用哈希表存储值对应的索引,随机删除的时候通过哈希表获取索引值,然后和列表最后一个元素进行交换,然后删除列表最后一个元素,不涉及到数组中元素的移动,因此在常数时间下即可完成,同时更新哈希表索引信息,从而实现O(1)复杂度下的随机删除。

解题代码

/**
 * @description:
 * @author: lilang
 * @version:
 * @modified By:1170370113@qq.com
 */
public class RandomizedSet {


    HashMap<Integer, Integer> dict;
    ArrayList<Integer> list;

    Random rand = new Random();


    public RandomizedSet() {
        list = new ArrayList<>();
        dict = new HashMap<>();
    }


    public boolean insert(int val) {


        if (dict.containsKey(val)) {
            return false;
        }

        dict.put(val, list.size());

        list.add(val);

        return true;
    }


    public boolean remove(int val) {


        if (!dict.containsKey(val)) {
            return false;
        }

        int lastVal = list.get(list.size() - 1);

        int valIndex = dict.get(val);

        list.set(valIndex, lastVal);

        dict.put(lastVal, valIndex);

        list.remove(list.size() - 1);
        dict.remove(val);

        return true;

    }


    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }


}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部