leetcode Insert Delete GetRandom O(1)
Design a data structure that supports all following operations in O(1) time.
insert(val)
: Inserts an item val to the set if not already present.remove(val)
: Removes an item val from the set if present.getRandom
: Returns a random element from current set of elements. Each element must have the same probability of being returned.Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 // Init an empty set.
RandomizedSet randomSet = new RandomizedSet();
// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);
// Returns false as 2 does not exist in the set.
randomSet.remove(2);
// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);
// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();
// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);
// 2 was already in the set, so return false.
randomSet.insert(2);
// Since 1 is the only number in the set, getRandom always return 1.
randomSet.getRandom();
题目大意: 要求实现一个数据结构,可以支持插入,删除,随机数生成。 他们的复杂度均要求O(1)
思路:用hash记录下标, 删除只需要和末尾元素调换即可
ps :无聊身边没电脑用手机1A了此题。。。还发了blog
1 | import random |
本题是leetcode 380 Insert Delete GetRandom O(1)的题解
更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/