力扣经典150题第十二题：O(1) 时间插入、删除和获取随机元素

用户8589624

发布于 2025-11-13 15:41:47

1620

文章被收录于专栏：nginxnginx

力扣经典150题第十二题：O(1) 时间插入、删除和获取随机元素

1. 简介

本文介绍如何设计实现一个支持在 O(1) 时间复杂度内进行插入、删除和获取随机元素的数据结构 RandomizedSet。我们将探讨数据结构的设计思路、核心算法以及代码实现，并给出相关的代码示例和时间复杂度分析。

2. 问题描述

给定一个数据结构 RandomizedSet，要求实现以下功能：

RandomizedSet()：初始化 RandomizedSet 对象。
bool insert(int val)：向集合中插入元素 val，如果元素已存在则返回 false，否则返回 true。
bool remove(int val)：从集合中移除元素 val，如果元素存在则返回 true，否则返回 false。
int getRandom()：随机返回集合中的一个元素，保证集合非空。

3. 数据结构设计

为了实现 O(1) 时间复杂度的插入、删除和获取随机元素，我们选择使用哈希表（HashMap）和动态数组（ArrayList）：

哈希表 valToIndex 用于存储元素值到在动态数组中的索引的映射。
动态数组 nums 用于存储集合中的元素，支持随机访问。

4. 核心思想

插入操作 insert(int val)：利用哈希表快速检查元素是否存在，如果不存在则将元素添加到动态数组末尾，并更新哈希表中的映射。
删除操作 remove(int val)：同样利用哈希表检查元素是否存在，如果存在则将该元素与动态数组末尾的元素交换位置，然后删除末尾元素，并更新哈希表中的映射。
获取随机元素 getRandom()：随机生成一个索引并返回对应的元素。

5. 具体实现

import java.util.*;

class RandomizedSet {
    List<Integer> nums;
    Map<Integer, Integer> valToIndex;
    Random rand;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        nums = new ArrayList<>();
        valToIndex = new HashMap<>();
        rand = 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 (valToIndex.containsKey(val))
            return false;
        
        nums.add(val);
        valToIndex.put(val, nums.size() - 1);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!valToIndex.containsKey(val))
            return false;
        
        int index = valToIndex.get(val);
        int lastVal = nums.get(nums.size() - 1);
        
        // Swap val with the last element in nums
        nums.set(index, lastVal);
        valToIndex.put(lastVal, index);
        
        // Remove val from nums and update map
        nums.remove(nums.size() - 1);
        valToIndex.remove(val);
        
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        return nums.get(rand.nextInt(nums.size()));
    }
}