前言

今天學哈希表，然后就第一節晚修趕快寫完作業就上了做題了，然后就做完了這道題get√。

---

正題

---

題目

給出兩個集合：
A是B的一個真子集，輸出“A is a proper subset of B”
B是A的一個真子集，輸出“B is a proper subset of A”
A和B是同一個集合，輸出“A equals B”
A和B的交集為空，輸出“A and B are disjoint”
上述情況都不是，輸出“I’m confused!”
然后集合大小小于10^5，集合中的數大小小于10^9

---

輸入輸出（建議無視）

Input

輸入有兩行，分別表示兩個集合，每行的第一個整數為這個集合的元素個數（至少一個），然后緊跟著這個集合的元素（均為不同的正整數）

Output

只有一行，就是A、B的關系。

Sample Input

樣例1
2 55 27
2 55 27
樣例2
3 9 24 1995
2 9 24
樣例3
3 1 2 3
4 1 2 3 4
樣例4
3 1 2 3
3 4 5 6
樣例5
2 1 2
2 2 3

Sample Output

樣例1
A equals B
樣例2
B is a proper subset of A
樣例3
A is a proper subset of B
樣例4
A and B are disjoint
樣例5
I’m confused!

---

解題思路

二分查找+快排

這就是用快排排好第一個集合然后用二分查找找另一個集合里的數。

（正題）哈希表

用哈希表儲存第一個集合，然后快速判斷集合中有沒有另一個集合中的數

---

代碼

二分查找+快排

#include<cstdio> #include<algorithm>//c++算法庫自帶快排 using namespace std; int n1,n2,a1[100001],a2[100001],l,r,ans,s,mid; char c; int main() {scanf("%d",&n1);for (int i=1;i<=n1;i++){scanf("%d",&a1[i]);}scanf("%d",&n2);for (int i=1;i<=n2;i++){scanf("%d",&a2[i]);}sort(a1+1,a1+1+n1);//快排for (int i=1;i<=n2;i++){ans=a2[i];//查找對象l=1;r=n1;//范圍while (l<=r){mid=(l+r)/2;//取中間值if (a1[mid]==ans) break;//找到就退出if (a1[mid]<ans) l=mid+1;else r=mid-1;//縮小范圍}if (a1[mid]==ans) s++;//統計相同數}//以下輸出不解釋if (s==n1 && s==n2) printf("A equals B");else if (s==n1) printf("A is a proper subset of B");else if (s==n2) printf("B is a proper subset of A");else if (s==0) printf("A and B are disjoint");else printf("I'm confused!"); }

哈希表

#include<cstdio> #include<algorithm> using namespace std; const int maxn=149993;//開個大一些的素數減少沖突 int n1,n2,hash[maxn],x,s; int hashmath(int x) {return x%maxn; }//哈希函數 int locate(int x)//尋找位置 {int i=0,w=hashmath(x);while (i<maxn && hash[(w+i)%maxn]!=0 && hash[(w+i)%maxn]!=x)//找到空位，相同的或沒有空位（數組開大已經避免了）i++;//下一個return (w+i)%maxn;//返回值 } void ins(int x)//插入函數 {int w=locate(x);//尋找位置hash[w]=x;//插入 } bool find(int x)//查找 {int w=locate(x);//尋找位置if (hash[w]==x) return true;//是否存在else return false; } int main() {scanf("%d",&n1);for (int i=1;i<=n1;i++){scanf("%d",&x);ins(x);//插入}scanf("%d",&n2);for (int i=1;i<=n2;i++){scanf("%d",&x);if (find(x)) s++;//統計次數}//以下輸出if (s==n1 && s==n2) printf("A equals B");else if (s==n1) printf("A is a proper subset of B");else if (s==n2) printf("B is a proper subset of A");else if (s==0) printf("A and B are disjoint");else printf("I'm confused!"); }

總結

以上是生活随笔為你收集整理的ssl1125-集合【哈希表二分查找+快排】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。