삽입 삭제 GetRandom O(1) - C++에서 중복 허용

어떤 연산을 지원하는 데이터 구조를 만들고 싶다고 가정하고, 이러한 연산은 O(1) 시간 동안 수행되어야 합니다. 따라서 이러한 작업은 다음과 같습니다. -

• insert(x):컬렉션에 x 삽입
• remove(x):컬렉션에서 x 삭제
• getRandom():컬렉션에서 임의의 요소를 찾습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 배열 번호 만들기
• 하나의 지도 만들기
• insert() 함수를 정의하면 val이 필요합니다.
• ret :=val이 m에 없을 때
• m[val] 끝에 숫자 크기 삽입
• insert { val, size of m[val] – 숫자 끝에 1} 쌍
• 반환
• remove() 함수를 정의하면 val이 필요합니다.
• ret :=val이 m에 없을 때
• ret가 0이 아니면 -
  • 마지막 =숫자의 마지막 요소
  • m[마지막 키][마지막 값] :=m[val]의 마지막 요소
  • nums[[m[val]]의 마지막 요소:=마지막
  • m[val]에서 마지막 요소 삭제
  • m[val]이 비어 있으면 -
    • m에서 val 삭제
  • 숫자에서 마지막 요소 삭제
• 반환
• getRandom() 함수 정의
• 컬렉션에서 임의의 요소 1개 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class RandomizedCollection {
public:
   vector <pair <int, int>> nums;
   unordered_map <int, vector<int>> m;
   RandomizedCollection() {
   }
   bool insert(int val) {
      bool ret = m.find(val) == m.end();
      m[val].push_back(nums.size());
      nums.push_back({val, m[val].size() - 1});
      return ret;
   }
   bool remove(int val) {
      bool ret = m.find(val) != m.end();
      if(ret){
         pair <int, int> last = nums.back();
         m[last.first][last.second] = m[val].back();
         nums[m[val].back()] = last;
         m[val].pop_back();
         if(m[val].empty())m.erase(val);
         nums.pop_back();
      }
      return ret;
   }
   int getRandom() {
      return nums[rand() % nums.size()].first;
   }
};
main(){
   RandomizedCollection ob;
   ob.insert(10);
   ob.insert(35);
   ob.insert(20);
   ob.insert(40);
   cout << (ob.getRandom()) << endl;
   ob.remove(20);
   cout << (ob.getRandom()) << endl;
}

입력

Insert 10, 35, 20, 40, then get one random number, say 40, then remove 20, again get random element, that is say 35.

출력

40
35