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

目录

• • 力扣经典150题第十二题：O(1) 时间插入、删除和获取随机元素
  • • 1. 简介
    • 2. 问题描述
    • 3. 数据结构设计
    • 4. 核心思想
    • 5. 具体实现
    • 6. 时间复杂度分析
    • 7. 应用和扩展
    • 8. 总结
    • 9. 参考资料

力扣经典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()));
    }
}

6. 时间复杂度分析

• 插入操作 insert(int val)：平均时间复杂度为 O(1)。
• 删除操作 remove(int val)：平均时间复杂度为 O(1)。
• 获取随机元素 getRandom()：平均时间复杂度为 O(1)。

7. 应用和扩展

RandomizedSet 可以应用于需要高效插入、删除和随机访问元素的场景，例如实现数据流的抽样操作或需要随机化处理元素顺序的算法。

8. 总结

本文介绍了如何

设计实现一个支持 O(1) 时间复杂度的数据结构 RandomizedSet，通过哈希表和动态数组的结合实现了快速的插入、删除和随机访问操作。该数据结构在实际应用中具有广泛的适用性，能够有效地解决相关问题。

9. 参考资料

• LeetCode 官网
• 算法导论