Insert Delete Get Random

380. 时间插入、删除和获取随机元素

插入操作：
- 使用哈希表来存储元素及其索引，在 O(1) 时间内检查元素是否存在，并在数组末尾插入新元素
删除操作：
- 对于删除操作，不直接从哈希表中删除元素，而是用数组末尾的元素替代被删除的元素。这样可以在 O(1) 时间内移除元素，而不需要移动数组中的其它元素
随机访问操作：
- 使用一个数组来存储所有元素，借助数组的随机访问特性，可以在 O(1) 时间内获取一个随机元素

时间复杂度

insert(val)：哈希表的查找和插入操作都是 O(1)，数组的末尾插入也是 O(1)
remove(val)：删除操作中的查找、替换和哈希表更新都是 O(1)，数组末尾删除是 O(1)
getRandom()：通过 rand() 和数组索引的方式随机获取元素是 O(1)

空间复杂度

空间复杂度为 O(n)

C++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


class RandomizedSet
{
public:
    std::unordered_map<int, int> hash;  // 存储元素及其索引
    std::vector<int> nums;  // 存储元素，支持随机访问

    // 初始化 RandomizedSet 对象
    RandomizedSet() {}

    // 插入元素 val
    bool insert(int val)
    {
        if (hash.count(val) == 0)
        {
            nums.push_back(val);  // 将 val 加入 nums 数组
            hash[val] = nums.size() - 1;  // 记录 val 在 nums 数组中的索引
            return true;
        }
        return false;
    }

    // 移除元素 val
    bool remove(int val)
    {
        if (hash.count(val))
        {
            int tail = nums.back();  // 获取数组末尾的元素
            int val_index = hash[val];  // 获取 val 在 nums 数组中的索引
            int tail_index = hash[tail];  // 获取数组末尾元素的索引

            // 将 val 和数组末尾元素交换
            std::swap(nums[val_index], nums[tail_index]);
            std::swap(hash[val], hash[tail]);

            nums.pop_back();  // 移除数组末尾元素
            hash.erase(val);  // 从哈希表中移除 val
            return true;
        }
        return false;
    }

    // 随机返回一个元素
    int getRandom()
    {
        return nums[rand() % nums.size()];  // 随机返回 nums 数组中的一个元素
    }
};

Python 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


import random

class RandomizedSet:
    def __init__(self):
        self.val_to_idx = {}
        self.nums = []

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

    def remove(self, val: int) -> bool:
        if val not in self.val_to_idx:
            return False
        idx = self.val_to_idx[val]
        last_val = self.nums[-1]
        self.nums[idx] = last_val
        self.val_to_idx[last_val] = idx
        self.nums.pop()
        del self.val_to_idx[val]
        return True

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

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


package main

import (
  "math/rand"
)

type RandomizedSet struct {
  valToIdx map[int]int
  nums []int
}

func Constructor() RandomizedSet {
  return RandomizedSet{
    valToIdx: make(map[int]int),
    nums: []int{},
  }
}

func (this *RandomizedSet) Insert(val int) bool {
  if _, exists := this.valToIdx[val]; exists {
    return false
  }
  this.nums = append(this.nums, val)
  this.valToIdx[val] = len(this.nums) - 1
  return true
}


func (this *RandomizedSet) Remove(val int) bool {
  idx, exists := this.valToIdx[val];
  if !exists {
    return false
  }
  last := this.nums[len(this.nums) - 1]
  this.nums[idx] = last
  this.valToIdx[last] = idx
  this.nums = this.nums[:len(this.nums) - 1]
  delete(this.valToIdx, val)
  return true
}

func (this *RandomizedSet) GetRandom() int {
  return this.nums[rand.Intn(len(this.nums))]
}