380. Insert Delete GetRandom O(1)

Problem Statement

link: LeetCode.cn LeetCode

Implement the RandomizedSet class:

RandomizedSet() Initializes the RandomizedSet object. bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise. bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise. int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned. You must implement the functions of the class such that each function works in average O(1) time complexity.

Example:

Input: ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"][[], [1], [2], [2], [], [1], [2], []] Output: [null, true, false, true, 2, true, false, 2]

Solution Approach

To achieve average O(1) time complexity for the insert, remove, and getRandom operations, we can utilize a combination of a list and a dictionary to store elements and their indices.

Algorithm

1. Initialize two data structures: a list (self.list) to store elements and a dictionary (self.map) to map elements to their indices in the list.
2. For the insert operation: Check if the element val is already present in self.map. If it is, return False; otherwise, append val to self.list, map it to its index in self.map, and return True.
3. For the remove operation: Check if the element val is present in self.map. If it is not, return False; otherwise, retrieve its index from self.map, update the last element of self.list to the position of the element to be removed, update the index of the last element in self.map accordingly, delete the last element from self.list, and delete the element val from self.map. Return True.
4. For the getRandom operation: Generate a random index within the range of the length of self.list, and return the element at that index.

Implement

    class RandomizedSet:
      def __init__(self):
          self.list = []
          self.map = {}

      def insert(self, val: int) -> bool:
          if val in self.map:
              return False
          else:
              self.list.append(val)
              self.map[val] = len(self.list) - 1
              return True
      
      def remove(self, val: int) -> bool:
          if val not in self.map:
              return False
          index = self.map[val]
          # self.list[index],self.list[-1] = self.list[-1], self.list[index]this is not right
          last = self.list[-1]
          self.list[index] = last
          self.map[last] = index
          del self.list[-1]
          del self.map[val]
          return True

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

    
    

Twitter  facebook  Email