| 68 | import random |
| 69 | |
| 70 | class RandomizedSet(object): |
| 71 | |
| 72 | def __init__(self): |
| 73 | """ |
| 74 | Initialize your data structure here. |
| 75 | """ |
| 76 | self.data_dict = {} |
| 77 | self.data_list = [] |
| 78 | self.length = 0 |
| 79 | |
| 80 | def insert(self, val): |
| 81 | """ |
| 82 | Inserts a value to the set. Returns true if the set did not already contain the specified element. |
| 83 | :type val: int |
| 84 | :rtype: bool |
| 85 | """ |
| 86 | if self.data_dict.get(val) is not None: |
| 87 | return False |
| 88 | |
| 89 | self.data_dict[val] = self.length |
| 90 | self.length += 1 |
| 91 | self.data_list.append(val) |
| 92 | |
| 93 | return True |
| 94 | |
| 95 | def remove(self, val): |
| 96 | """ |
| 97 | Removes a value from the set. Returns true if the set contained the specified element. |
| 98 | :type val: int |
| 99 | :rtype: bool |
| 100 | """ |
| 101 | |
| 102 | if self.data_dict.get(val) is not None: |
| 103 | x = self.data_dict.pop(val) |
| 104 | y = self.data_list[-1] |
| 105 | if y != val: |
| 106 | |
| 107 | self.data_dict[y] = x |
| 108 | self.data_list[-1], self.data_list[x] = self.data_list[x], self.data_list[-1] |
| 109 | |
| 110 | self.data_list.pop() |
| 111 | self.length -= 1 |
| 112 | |
| 113 | return True |
| 114 | |
| 115 | return False |
| 116 | |
| 117 | def getRandom(self): |
| 118 | """ |
| 119 | Get a random element from the set. |
| 120 | :rtype: int |
| 121 | """ |
| 122 | |
| 123 | return self.data_list[random.randint(0, self.length-1)] |
| 124 | |
| 125 | |
| 126 | # Your RandomizedSet object will be instantiated and called as such: |
nothing calls this directly
no outgoing calls
no test coverage detected