Chèn Xóa GetRandom O (1) - Các bản sao được phép trong C ++

Giả sử, chúng ta muốn tạo một cấu trúc dữ liệu, hỗ trợ một số hoạt động, các hoạt động này phải được định dạng trước trong khoảng thời gian là O (1). Vì vậy, hãy để những hoạt động này giống như -

• insert (x):chèn x vào bộ sưu tập
• remove (x):xóa x khỏi bộ sưu tập
• getRandom ():Điều này sẽ tìm thấy phần tử ngẫu nhiên tạo thành bộ sưu tập đó.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một số mảng
• tạo một bản đồ m
• Xác định một hàm insert (), điều này sẽ chiếm giá trị,
• ret:=khi val không ở trong m
• chèn kích thước của nums vào cuối m [val]
• chèn cặp {val, size of m [val] - 1} vào cuối nums
• trả lời lại
• Xác định một hàm remove (), hàm này sẽ lấy giá trị,
• ret:=khi val không ở trong m
• nếu ret khác 0, thì -
  • last =phần tử cuối cùng của nums
  • m [key of last] [value of last]:=phần tử cuối cùng của m [val]
  • nums [phần tử cuối cùng của [m [val]]:=last
  • xóa phần tử cuối cùng khỏi m [val]
  • nếu m [val] trống, thì -
    • xóa val khỏi m
  • xóa phần tử cuối cùng khỏi nums
• trả lời lại
• Xác định một hàm getRandom ()
• trả về một phần tử ngẫu nhiên từ bộ sưu tập

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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;
}

Đầu vào

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

Đầu ra

40
35