a174 - 上帝玩不玩骰子？
題目描述
題目要求模擬一個簡單的雜湊表。雜湊表使用模運算將數字分配到不同的區間，並支持插入、刪除和輸出整個雜湊表的功能。插入時，如果數字已經存在，則忽略插入操作。刪除時，如果數字不存在，則忽略刪除操作。
解題思路
使用一個 set 的陣列來模擬雜湊表。陣列的索引代表雜湊表的區間，每個區間使用 set 儲存該區間內的數字。set 確保了區間內的數字是有序的，並且可以方便地進行插入和刪除操作。
對於每個操作：
- 如果操作是 1，則計算數字模 m 的值，將數字插入對應區間的
set中。 - 如果操作是 2，則計算數字模 m 的值，從對應區間的
set中刪除數字。 - 如果操作是 3，則遍歷整個雜湊表，輸出每個區間的數字（由小到大）。
複雜度分析
- 時間複雜度: O(k * (1 + log m))，其中 k 是操作的數量，m 是雜湊表的區間數量。插入和刪除操作在
set中的時間複雜度是 O(log m)，輸出操作的時間複雜度是 O(m)。 - 空間複雜度: O(m * n)，其中 m 是雜湊表的區間數量，n 是每個區間中儲存的數字的最大數量。
程式碼
#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";
}
}
}
}