Insert Delete GetRandom O(1) อนุญาตซ้ำใน C++

ภาพรวมปัญหา

ออกแบบโครงสร้างข้อมูลที่รองรับการทำงาน 3 แบบในเวลา O(1) เฉลี่ย:
1. insert(val) — เพิ่มค่า (อนุญาตซ้ำ)
2. remove(val) — ลบค่า 1 ตัว (ถ้ามี)
3. getRandom() — สุ่มคืนค่าจากชุดข้อมูลปัจจุบัน (โอกาสเท่ากันทุกตัว)

วิธีแก้ปัญหา: Vector + Hash Map

• Vector nums: เก็บคู่ {value, index_in_map_vector} เพื่อ random access และ swap-last ได้
• Hash Map m[val]: เก็บ vector ของ indices ใน nums ที่มีค่า val

รายละเอียดการทำงาน

insert(val)

1. ret = (val ไม่อยู่ใน m)
2. เพิ่ม nums.size() เข้า m[val]
3. เพิ่ม {val, m[val].size()-1} เข้า nums
4. คืน ret

remove(val)

1. ret = (val อยู่ใน m)
2. ถ้า ret:
   • last = nums.back()
   • อัปเดต index ของ last ใน m[last.first] ให้ชี้ไปที่ตำแหน่งของ val ที่จะลบ
   • swap nums[m[val].back()] กับ last
   • ลบ index สุดท้ายออกจาก m[val]
   • ถ้า m[val] ว่าง → ลบ key val ออกจาก map
   • nums.pop_back()
3. คืน ret

getRandom()

คืน nums[rand() % nums.size()].first

โค้ด 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;
}

การวิเคราะห์ความซับซ้อน

• เวลา: O(1) เฉลี่ยสำหรับทุก operation
• พื้นที่: O(n) — n = จำนวนองค์ประกอบทั้งหมด