380. Insert Delete GetRandom O(1)

Implement the RandomizedSet class:

• 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.

Follow up: Could you implement the functions of the class with each function works in average O(1) time?

My Answer 1: Accepted (Runtime: 452 ms - 7.82% / Memory Usage: 18.9 MB - 6.26%)

class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.randomizedset = set()

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val in self.randomizedset:
            return False
        else:
            self.randomizedset.add(val)
            return True

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val in self.randomizedset:
            self.randomizedset.remove(val)
            return True
        else:
            return False

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        randomlist = random.sample(self.randomizedset, 1)
        return randomlist[0]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

• init: set 생성

• insert: 중복 있으면 return False, 없으면 add 후 return True

• remove: 삭제하고자 하는 값이 있으면 remove 후 return True, 없으면 return False

• getRandom: random.sample 이용해서 1개의 랜덤값 정하고 return
  (random.sample 은 리스트로 반환하기 때문에 첫번째 값인 randomlist[0] 을 return)

런타임 실화??

convert the data into a python list in order to return a random element 때문이라고 한다.
remove is not O(1) 이기도...

Solution 1: Runtime: 96 ms - 76.01% / Memory Usage: 18.5 MB - 22.61%

class RandomizedSet:

    def __init__(self):
        self.data_map = {} # dictionary, aka map, aka hashtable, aka hashmap
        self.data = [] # list aka array

    def insert(self, val: int) -> bool:

        # the problem indicates we need to return False if the item 
        # is already in the RandomizedSet---checking if it's in the
        # dictionary is on average O(1) where as
        # checking the array is on average O(n)
        if val in self.data_map:
            return False

        # add the element to the dictionary. Setting the value as the 
        # length of the list will accurately point to the index of the 
        # new element. (len(some_list) is equal to the index of the last item +1)
        self.data_map[val] = len(self.data)

        # add to the list
        self.data.append(val)
        
        return True

    def remove(self, val: int) -> bool:

        # again, if the item is not in the data_map, return False. 
        # we check the dictionary instead of the list due to lookup complexity
        if not val in self.data_map:
            return False

        # essentially, we're going to move the last element in the list 
        # into the location of the element we want to remove. 
        # this is a significantly more efficient operation than the obvious 
        # solution of removing the item and shifting the values of every item 
        # in the dicitionary to match their new position in the list
        last_elem_in_list = self.data[-1]
        index_of_elem_to_remove = self.data_map[val]

        self.data_map[last_elem_in_list] = index_of_elem_to_remove
        self.data[index_of_elem_to_remove] = last_elem_in_list

        # change the last element in the list to now be the value of the element 
        # we want to remove
        self.data[-1] = val

        # remove the last element in the list
        self.data.pop()

        # remove the element to be removed from the dictionary
        self.data_map.pop(val)
        return True

    def getRandom(self) -> int:
        # if running outside of leetcode, you need to `import random`.
        # random.choice will randomly select an element from the list of data.
        return random.choice(self.data)


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

• init: [딕셔너리] data_map & [리스트] data 두개를 만들어줌

• insert: 삽입하려는 값이 data_map 에 있으면 return False, 없으면 data_map 과 data 에 값을 넣어줌

• remove: 삭제하려는 값이 data_map 에 없으면 return False, 있으면 (remove 함수를 사용하지 않고)
  data 의 마지막에 위치한 값과 data_map 에서의 val index 를 구해서
  삭제할 값과 마지막에 insert 한 값의 위치를 바꿔주기
  data_map[last_elem_in_list] = index_of_elem_to_remove
  data[index_of_elem_to_remove] = last_elem_in_list
  self.data[-1] = val
  해준 후 pop 을 이용해 val 삭제

  last element 와 index 변환 안해주면 data 의 인덱스들 꼬여서 wrong answer 된다

• getRandom: random.choice 를 이용