Insert Delete GetRandom O(1) - Cho phép trùng lặp trong C++

Thiết kế cấu trúc dữ liệu hỗ trợ 3 thao tác O(1) trung bình:

• insert(val): chèn giá trị, trả về true nếu chưa tồn tại.
• remove(val): xóa một lần xuất hiện, trả về true nếu tồn tại.
• getRandom(): trả về phần tử ngẫu nhiên từ tập hợp (mỗi phần tử có xác suất đều).

Cho phép trùng lặp — khác với phiên bản không trùng lặp.

Cấu trúc dữ liệu

• vector<pair<int, int>> nums: lưu {value, index_in_map_vector}.
• unordered_map<int, vector<int>> m: ánh xạ giá trị → danh sách chỉ số trong nums.

Ý tưởng cốt lõi

Xóa O(1): Hoán đổi phần tử cần xóa với phần tử cuối của nums, cập nhật chỉ số trong m, rồi pop_back().

Chi tiết

insert(val)

ret = (val not in m)
m[val].push_back(nums.size())
nums.push_back({val, m[val].size() - 1})
return ret

remove(val)

ret = (val in m)
if ret:
    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

getRandom()

return nums[rand() % nums.size()].first

Cài đặt C++

#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, (int)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;
    }
};

int 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;
    return 0;
}

Độ phức tạp

• Thời gian trung bình: O(1) cho mọi thao tác.
• Không gian: O(n) — lưu tất cả phần tử.

Input / Output

Insert 10, 35, 20, 40 → getRandom() = 40 → remove(20) → getRandom() = 35
Output: 40 35