本文共 1414 字，大约阅读时间需要 4 分钟。

设计一个数据结构，使得能够在O(1)的时间复杂度中插入、删除数字，以及随机获取一个数字。所有数字都能被等概率的随机出来。

思路和代码

为了实现O(1)的插入、删除和随机查询，结合使用哈希表和双向链表的思路。哈希表用于快速查找和插入，双向链表用于维护元素的顺序，确保随机查询的概率公平。

插入操作

• 使用哈希表快速查找元素是否存在。
• 如果不存在，插入到双向链表的末尾，并记录在哈希表中。

删除操作

• 使用哈希表快速查找元素位置。
• 使用伪删除法，将被删除元素的位置替换为链表末尾元素的值，然后删除链表末尾的元素。
• 更新哈希表，删除被删除元素的记录。

随机查询操作

• 根据链表长度生成随机索引。
• 通过链表获取该索引位置的元素。

代码实现

import java.util.*;public class RandomizedSet {    private final List
   
     list;    private final Map
    
      hash;    public RandomizedSet() {        list = new ArrayList<>();        hash = new HashMap<>();    }    public boolean insert(int val) {        if (hash.containsKey(val)) {            return false;        }        list.add(val);        hash.put(val, list.size() - 1);        return true;    }    public boolean remove(int val) {        if (!hash.containsKey(val)) {            return false;        }        int position = hash.get(val);        if (position != list.size() - 1) {            int last = list.get(list.size() - 1);            list.set(position, last);            hash.put(last, position);        }        list.remove(list.size() - 1);        hash.remove(val);        return true;    }    public int getRandom() {        int position = (int) Math.floor(Math.random() * list.size());        return list.get(position);    }}
    
   

解释

• 插入操作：检查元素是否存在，不存在则插入到链表末尾，记录在哈希表中。
• 删除操作：使用伪删除法，避免链表大范围调整，确保O(1)时间复杂度。
• 随机查询：根据链表长度生成随机索引，确保每个元素等概率被选中。

该数据结构通过结合哈希表和双向链表，实现了高效的插入、删除和随机查询操作。