题目描述

设计一个支持以下操作的数据结构：

1. Insert(val)：向数据结构中插入一个元素，如果元素已存在则不进行任何操作。
2. Remove(val)：从数据结构中删除一个元素，如果元素不存在则不进行任何操作。
3. GetRandom()：随机返回数据结构中的一个元素，每个元素被返回的概率相同。

要求所有操作的时间复杂度均为 O(1)。

解题思路

为了满足所有操作的时间复杂度为 O(1)，我们可以使用哈希表（HashMap）来存储元素及其存在性，同时使用一个动态数组（ArrayList 或 List）来存储所有元素的值，以确保能够随机访问。

• 哈希表：用于快速判断元素是否存在，并实现 O(1) 的插入和删除。
• 动态数组：用于存储所有元素，通过随机索引实现 O(1) 的随机访问。

示例代码

PHP 示例

class RandomizedCollection {
    private $nums;
    private $valMap;

    function __construct() {
        $this->nums = [];
        $this->valMap = [];
    }

    function insert($val) {
        if (!isset($this->valMap[$val])) {
            $this->valMap[$val] = [];
        }
        
        if (!in_array($val, $this->nums)) {
            $this->nums[] = $val;
            $this->valMap[$val][] = count($this->nums) - 1;
            return true;
        }
        
        return false;
    }

    function remove($val) {
        if (!isset($this->valMap[$val]) || empty($this->valMap[$val])) {
            return false;
        }
        
        $indexToRemove = array_pop($this->valMap[$val]);
        $lastVal = end($this->nums);
        
        // Swap with the last element and pop
        $this->nums[$indexToRemove] = $lastVal;
        array_pop($this->nums);
        
        // Update the index map for the last element
        $lastValIndex = array_search($lastVal, $this->valMap[$lastVal]);
        $this->valMap[$lastVal][$lastValIndex] = $indexToRemove;
        
        if (empty($this->valMap[$val])) {
            unset($this->valMap[$val]);
        }
        
        return true;
    }

    function getRandom() {
        $randIndex = array_rand($this->nums);
        return $this->nums[$randIndex];
    }
}

Python 示例

import random

class RandomizedCollection:
    def __init__(self):
        self.nums = []
        self.valMap = {}

    def insert(self, val: int) -> bool:
        if val not in self.valMap:
            self.valMap[val] = []
        
        if val not in self.nums:
            self.nums.append(val)
            self.valMap[val].append(len(self.nums) - 1)
            return True
        
        return False

    def remove(self, val: int) -> bool:
        if val not in self.valMap or not self.valMap[val]:
            return False
        
        index_to_remove = self.valMap[val].pop()
        last_val = self.nums[-1]
        
        # Swap with the last element and pop
        self.nums[index_to_remove] = last_val
        self.nums.pop()
        
        # Update the index map for the last element
        if last_val in self.valMap:
            last_val_index = self.valMap[last_val].index(len(self.nums))
            self.valMap[last_val][last_val_index] = index_to_remove
        
        if not self.valMap[val]:
            del self.valMap[val]
        
        return True

    def getRandom(self) -> int:
        return random.choice(self.nums)

JavaScript 示例

class RandomizedCollection {
    constructor() {
        this.nums = [];
        this.valMap = new Map();
    }

    insert(val) {
        if (!this.valMap.has(val)) {
            this.valMap.set(val, []);
        }
        
        if (!this.nums.includes(val)) {
            this.nums.push(val);
            this.valMap.get(val).push(this.nums.length - 1);
            return true;
        }
        
        return false;
    }

    remove(val) {
        if (!this.valMap.has(val) || this.valMap.get(val).length === 0) {
            return false;
        }
        
        const indexToRemove = this.valMap.get(val).pop();
        const lastVal = this.nums[this.nums.length - 1];
        
        // Swap with the last element and pop
        this.nums[indexToRemove] = lastVal;
        this.nums.pop();
        
        // Update the index map for the last element
        if (this.valMap.has(lastVal)) {
            const lastIndex = this.valMap.get(lastVal).findIndex(idx => idx === this.nums.length);
            this.valMap.get(lastVal)[lastIndex] = indexToRemove;
        }
        
        if (this.valMap.get(val).length === 0) {
            this.valMap.delete(val);
        }
        
        return true;
    }

    getRandom() {
        const randomIndex = Math.floor(Math.random() * this.nums.length);
        return this.nums[randomIndex];
    }
}

以上代码均实现了题目要求的功能，并且确保了所有操作的时间复杂度为 O(1)。