สมมุติว่าเราต้องการสร้างโครงสร้างข้อมูลที่รองรับการดำเนินการบางอย่าง การดำเนินการเหล่านี้จะต้องสร้างไว้ล่วงหน้าในระยะเวลา O(1) ดังนั้นให้การดำเนินการเหล่านี้เป็นเหมือน -
- insert(x):ใส่ x เข้าไปในคอลเลกชัน
- remove(x):ลบ x ออกจากคอลเล็กชัน
- getRandom():สิ่งนี้จะค้นหารูปแบบองค์ประกอบสุ่มที่คอลเลกชันนั้น
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างตัวเลขอาร์เรย์
- สร้างหนึ่งแผนที่ m
- กำหนดฟังก์ชัน insert() ซึ่งจะใช้ val
- ret :=เมื่อ val ไม่เป็น m
- ใส่ขนาดของ nums ที่ส่วนท้ายของ m[val]
- ใส่ { val, size of m[val] – 1} คู่ที่ส่วนท้ายของ nums
- คืนสินค้า
- กำหนดฟังก์ชัน remove() ซึ่งจะใช้ val
- ret :=เมื่อ val ไม่เป็น m
- ถ้า ret ไม่ใช่ศูนย์ ดังนั้น −
- last =องค์ประกอบสุดท้ายของ nums
- m[key of last][value of last] :=องค์ประกอบสุดท้ายของ m[val]
- nums[องค์ประกอบสุดท้ายของ [m[val]] :=สุดท้าย
- ลบองค์ประกอบสุดท้ายจาก m[val]
- ถ้า m[val] ว่างเปล่า ดังนั้น −
- ลบ val จาก m
- ลบองค์ประกอบสุดท้ายออกจาก nums
- คืนสินค้า
- กำหนดฟังก์ชัน getRandom()
- ส่งคืนองค์ประกอบสุ่มหนึ่งรายการจากคอลเล็กชัน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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
