資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中插入、刪除和獲取隨機數 O(1) - 允許重複
假設，我們想要建立一個支援某些操作的資料結構，這些操作必須在 O(1) 的時間內完成。所以這些操作例如：
- insert(x)：將 x 插入集合
- remove(x)：從集合中刪除 x
- getRandom()：這將從集合中找到隨機元素。
為了解決這個問題，我們將遵循以下步驟：
- 建立一個數組 nums
- 建立一個對映 m
- 定義一個函式 insert()，它將接收 val，
- ret := 當 val 不在 m 中時
- 在 m[val] 的末尾插入 nums 的大小
- 在 nums 的末尾插入 {val, m[val] 的大小 - 1} 對
- 返回 ret
- 定義一個函式 remove()，它將接收 val，
- ret := 當 val 不在 m 中時
- 如果 ret 不為零，則：
- last = nums 的最後一個元素
- m[last 的鍵][last 的值] := m[val] 的最後一個元素
- nums[m[val] 的最後一個元素] := last
- 從 m[val] 中刪除最後一個元素
- 如果 m[val] 為空，則：
- 從 m 中刪除 val
- 從 nums 中刪除最後一個元素
- 返回 ret
- 定義一個函式 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
更新於: 2020-06-01
101 次瀏覽
廣告