设计一个支持全O(1)的插入、删除和随机获取的数据结构-JZTXT

插入（Insert）：在 O(1) 时间内将一个元素插入集合中。
删除（Remove）：在 O(1) 时间内从集合中删除一个元素。
随机获取（GetRandom）：在 O(1) 时间内从集合中随机获取一个元素。
对于插入和删除操作，常见的数据结构是哈希表，因为哈希表可以在平均情况下提供 O(1) 的插入和删除操作。但是，对于随机获取操作，哈希表并不能直接提供 O(1) 的性能，因为哈希表中元素的位置是由哈希函数决定的，无法直接进行随机访问。

因此，我们需要一个数据结构，既能提供哈希表的快速插入和删除，又能够支持随机获取。一种常见的做法是使用数组，因为数组可以实现 O(1) 时间的随机访问。但是，直接使用数组的话，删除操作的平均时间复杂度就不再是 O(1)。

解决这个问题的一种方法是使用两个数据结构的结合：哈希表 + 数组。具体地，使用一个哈希表来存储元素到其在数组中的索引的映射，同时使用一个动态数组来存储元素。这样，插入和删除的操作可以在哈希表中完成，而随机获取的操作可以在数组中完成。

在具体实现中，插入操作需要在数组中添加元素，同时更新哈希表中的映射；删除操作需要在数组中删除元素，同时更新哈希表中的映射；随机获取操作可以通过在数组中随机选择一个索引，然后返回对应的元素来实现。

这就是这个问题的一种解法，其中哈希表和数组的结合使得插入、删除和随机获取这三种操作的平均时间复杂度都是 O(1)。

using System;
using System.Collections.Generic;

class RandomizedSet
{
    private List<int> nums;
    private Dictionary<int, int> numToIndex;

    public RandomizedSet()
    {
        nums = new List<int>();
        numToIndex = new Dictionary<int, int>();
    }

    public bool Insert(int val)
    {
        if (numToIndex.ContainsKey(val))
        {
            return false; // 已存在
        }

        nums.Add(val);
        numToIndex[val] = nums.Count - 1;
        return true;
    }

    public bool Remove(int val)
    {
        if (!numToIndex.ContainsKey(val))
        {
            return false; // 不存在
        }

        int lastNum = nums[nums.Count - 1];
        int index = numToIndex[val];

        // 将要删除的元素与最后一个元素交换
        nums[index] = lastNum;
        numToIndex[lastNum] = index;

        // 删除最后一个元素
        nums.RemoveAt(nums.Count - 1);
        numToIndex.Remove(val);

        return true;
    }

    public int GetRandom()
    {
        Random rand = new Random();
        int randomIndex = rand.Next(nums.Count);
        return nums[randomIndex];
    }
}

class Program
{
    static void Main()
    {
        RandomizedSet set = new RandomizedSet();

        Console.WriteLine(set.Insert(1)); // 返回 true
        Console.WriteLine(set.Remove(2)); // 返回 false
        Console.WriteLine(set.Insert(2)); // 返回 true
        Console.WriteLine(set.GetRandom()); // 随机返回 1 或 2
        Console.WriteLine(set.Remove(1)); // 返回 true
        Console.WriteLine(set.Insert(2)); // 返回 false，已存在
        Console.WriteLine(set.GetRandom()); // 随机返回 2
    }
}