380. Insert Delete GetRandom O(1)
Skills:
Array
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Để giải bài toán Insert Delete GetRandom O(1) trên LeetCode, chúng mình cần thiết kế một cấu trúc dữ liệu hỗ trợ ba thao tác sau trong thời gian trung bình O(1)
Approach
Solution
1class RandomizedSet {
2 private list: number[];
3 private hashmap: Map<number, number>; // {val: list.length}
4
5 constructor() {
6 this.list = [];
7 this.hashmap = new Map();
8 }
9
10 insert(val: number): boolean {
11 if (this.hashmap.has(val)) {
12 return false
13 }
14 this.list.push(val);
15 this.hashmap.set(val, this.list.length - 1);
16 return true;
17 }
18
19 remove(val: number): boolean {
20 if (!this.hashmap.has(val)) {
21 return false;
22 }
23
24 let index = this.hashmap.get(val)!;
25 const lastValue = this.list[this.list.length - 1];
26
27 this.list[index] = lastValue;
28 this.hashmap.set(lastValue, index);
29
30 this.hashmap.delete(val);
31 this.list.pop();
32
33 return true;
34 }
35
36 getRandom(): number {
37 const randomInt = Math.floor(Math.random() * this.list.length);
38 return this.list[randomInt];
39 }
40}
41
42/**
43 * Your RandomizedSet object will be instantiated and called as such:
44 * var obj = new RandomizedSet()
45 * var param_1 = obj.insert(val)
46 * var param_2 = obj.remove(val)
47 * var param_3 = obj.getRandom()
48 */