380. Insert Delete GetRandom O(1)
Tags:
Medium
Skills:
Array
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bạn cần thiết kế một lớp (class) cho phép thực hiện ba thao tác sau với độ phức tạp trung bình O(1):
Approach
Solution
1class RandomizedSet {
2 map: Map<number, number>;
3 arr: number[]
4
5 constructor() {
6 this.map = new Map();
7 this.arr = []
8 }
9
10 insert(val: number): boolean {
11 if (this.map.has(val)) return false;
12 this.map.set(val, this.arr.length);
13 this.arr.push(val);
14 return true
15 }
16
17 remove(val: number): boolean {
18 if (!this.map.has(val)) return false
19 const idx = this.map.get(val);
20 const last = this.arr.at(-1);
21 this.map.set(last, idx)
22
23 this.arr[idx] = last;
24 this.arr.pop();
25 this.map.delete(val)
26 return true
27 }
28
29 getRandom(): number {
30 const idx = Math.floor(Math.random() * this.arr.length)
31 return this.arr[idx];
32 }
33}
34
35/**
36 * Your RandomizedSet object will be instantiated and called as such:
37 * var obj = new RandomizedSet()
38 * var param_1 = obj.insert(val)
39 * var param_2 = obj.remove(val)
40 * var param_3 = obj.getRandom()
41 */