美文网首页
LeetCode 第380题:O(1) 时间插入、删除和获取随机

LeetCode 第380题:O(1) 时间插入、删除和获取随机

作者: 放开那个BUG | 来源:发表于2024-05-04 15:00 被阅读0次

    1、前言

    题目描述

    2、思路

    将最后一个元素放到移除元素的位置上,然后把最后一个元素删除就行,还要考虑最后一个是第一个情况

    3、代码

    class RandomizedSet {
    
        private Map<Integer, Integer> map = new HashMap<>();
        private List<Integer> list = new ArrayList<>();
        private Random random = new Random();
    
        public RandomizedSet() {
    
        }
    
        public boolean insert(int val) {
            if(map.containsKey(val)){
                return false;
            }
            list.add(val);
            map.put(val, list.size() - 1);
    
            return true;
        }
    
        public boolean remove(int val) {
            if(!map.containsKey(val)){
                return false;
            }
            // 将最后一个元素放到移除元素的位置上,
            // 然后把最后一个元素删除就行
            // 还要考虑最后一个是第一个情况
            int removeIndex = map.get(val);
            int lastIndex = list.size() - 1;
            int lastVal = list.get(lastIndex);
            list.set(removeIndex, lastVal);
            map.put(lastVal, removeIndex);
            list.remove(lastIndex);
            map.remove(val);
    
            return true;
        }
    
        public int getRandom() {
            int index = random.nextInt(list.size());
            return list.get(index);
        }
    
    }
    

    相关文章

      网友评论

          本文标题:LeetCode 第380题:O(1) 时间插入、删除和获取随机

          本文链接:https://www.haomeiwen.com/subject/prlnxjtx.html