[数据结构与算法] 每日一题:380. O(1) 时间插入、删除和获取随机元素

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 每日一题:380. O(1) 时间插入、删除和获取随机元素 -> 正文阅读

[数据结构与算法]每日一题:380. O(1) 时间插入、删除和获取随机元素

解题思路

利用List组合Map实现

代码

class RandomizedSet {
    //对应关系为值和其在List中的下标
    Map<Integer,Integer> map;
    List<Integer> list;
    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)){
            return false;
        }
        map.put(val,list.size());
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)){
            return false;
        }
        int last = list.get(list.size()-1);
        int index = map.get(val);
        //将val所在下标的值修改为list尾部的值
        list.set(index,last);
        map.put(last,index);
        //删除末尾元素
        list.remove(list.size()-1);
        //在Map集合中删除
        map.remove(val);
        return true;
    }

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