a175 - 撒旦玩不玩骰子？
題目描述
題目要求模擬一個簡單的 Hash Table，並實現插入、刪除和輸出功能。Hash Table 使用 mod m 的方式將數字分到 m 個區間，每個區間使用 set 儲存數字，以確保區間內的數字有序且不重複。
解題思路
使用一個 tb 結構，其中包含一個 set<int>，用於儲存每個區間的數字。程式首先讀取操作次數 k 和模數 m。然後，迴圈執行 k 次操作。
- 如果操作是 1，則讀取一個數字
n，計算n % m作為區間索引，並將n插入到對應區間的 set 中。如果n已經存在，則不進行插入。 - 如果操作是 2，則讀取一個數字
n，計算n % m作為區間索引，並從對應區間的 set 中刪除n。如果n不存在，則不進行刪除。 - 如果操作是 3，則輸出整個 Hash Table。對於每個區間，輸出區間索引和該區間 set 中的所有數字，數字之間用 " -> " 分隔，最後用 "NULL" 結尾。
複雜度分析
- 時間複雜度: O(k * log m)，其中 k 是操作次數，m 是模數。插入和刪除操作在 set 中的時間複雜度為 O(log m)，輸出操作的時間複雜度為 O(m)。
- 空間複雜度: O(m)，因為 Hash Table 儲存了 m 個區間，每個區間使用 set 儲存數字。
程式碼
#include <iostream>
#include <set>
using namespace std;
struct tb{
set <int> index;
};
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int k,m,is,n;
while(cin >> k >> m){
tb a[m];
while(k--){
cin >> is;
if(is == 1){
cin >> n;
a[n%m].index.insert(n);
}
else if(is == 2){
cin >> n;
a[n%m].index.erase(n);
}
else{
cout << "===== s =====\n";
for(int i=0;i<m;++i){
cout << "[" << i/100 << (i%100)/10 << i%10 << "]:";
for(auto j=a[i].index.begin();j!=a[i].index.end();++j){
cout << *j << " -> ";
}
cout << "NULL\n";
}
cout << "===== e =====\n";
}
}
}
}