[問題] 關於set的merge
我不清楚這個問題是不是應該在此版發問，因為有點像演算法或資料結構的問題
如果不妥或違反板規我會立刻刪文!
問題是這樣的：
我現在有兩個set(集合)，以array來實作，array中的元素沒有順序之分(因為是set)
其中set A 大小為M
set B 大小為N
M的大小遠大於N，其中M的大小約是N的平方倍
現在要寫一個演算法，創造一個set C，也是以array來實作
將A和B 聯集(Union)為C set
重點來了，此問題要求此演算法要盡量有效率
我的寫法如下：(虛擬碼)
int main()
{
int a[1..M];
int b[1..N];
int[] c = merge(a,b,M,N);
}
int[] merge(int a[], int b[], int M, int N)
{
int S=M+N;
int c[1..S]; //宣告C陣列，大小為M+N
for(int i=1;i<=M;i++) //把a陣列丟進c的前半部
c[i]=a[i];
for(int i=1;i<=N;i++) //把b陣列丟進c的後半部
c[M+i]=b[i];
return c;
}
這演算法就很直觀，也沒甚麼特別想法，就創一個M+N的array把元素都扔進來就對了
時間為O(N^2)，因為M的大小相當於N^2
不知道有沒有更好的解決方法? 我實在不了解這問題有甚麼特殊之處，但感覺有陷阱
謝謝各位抽空幫我解答!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.244.44.20
※ 編輯: flipsydee 來自: 60.244.44.20 (01/22 17:19)
※ 編輯: flipsydee 來自: 60.244.44.20 (01/22 17:20)
→
01/22 17:21, , 1F
01/22 17:21, 1F
→
01/22 17:22, , 2F
01/22 17:22, 2F
是union
其實我程式底子沒很好....以上那些是虛擬碼，我的用意是回傳C陣列給主程式..
※ 編輯: flipsydee 來自: 60.244.44.20 (01/22 17:25)
對不起，我好像發現問題了，既然是兩個set的union操作，應該要排除共同
的元素才是。那我以上的寫法都寫錯了...
※ 編輯: flipsydee 來自: 60.244.44.20 (01/22 17:28)
※ 編輯: flipsydee 來自: 60.244.44.20 (01/22 17:28)
推
01/22 17:32, , 3F
01/22 17:32, 3F
→
01/22 17:34, , 4F
01/22 17:34, 4F
推
01/22 17:36, , 5F
01/22 17:36, 5F
推
01/22 21:36, , 6F
01/22 21:36, 6F
我又寫了一個...網路上搜尋set union algorithm找到的資料很少...
只好自己寫了一個，可是很難看
版本一：為了省時間用線性時間排序與二分搜尋法
https://github.com/vacuumv/coding1/blob/master/test.c
版本二：網路上有人說可以用hashing table的想法去寫，又沒給code
所以我也自作聰明的寫了一個
https://github.com/vacuumv/coding1/blob/master/test2.c
小弟的程式概念很薄弱，還望大家不吝賜教......有錯的很誇張的觀念
也請多多包涵...
我只是在想這種常見的問題應該會有固定解法阿(最好的演算法)...有人知道嗎?
※ 編輯: flipsydee 來自: 60.244.44.20 (01/22 22:11)
推
01/22 22:28, , 7F
01/22 22:28, 7F
→
01/22 22:28, , 8F
01/22 22:28, 8F
→
01/22 22:28, , 9F
01/22 22:28, 9F
推
01/23 09:26, , 10F
01/23 09:26, 10F
→
01/23 09:26, , 11F
01/23 09:26, 11F
→
01/23 09:26, , 12F
01/23 09:26, 12F
那個好像是disjoint set的union才適用喔..
現在題目給的兩個set 可能非disjoint..
其實這是台大資管所102年計算機概論的題目~貼上原文，大家可以思考一下!
Design an algorithm that, given two sets of numbers, computes the union of
the two sets.
The first set of m numbers is given as an array A in no particular order and
the second set of n numbers as another array B also in no particular order.
The result should be represented as a third array C where no particular
ordering is required.
It is known that m is much larger than n, approximately in the order of n^2.
Please describe your algorithm in suitable pseudo code and analyze its time
complexity.
The more efficient your algorithm is, the more points you will be credited
for this problem.(15%)
※ 編輯: flipsydee 來自: 60.244.44.20 (01/23 11:14)
推
01/24 13:07, , 13F
01/24 13:07, 13F
→
01/24 13:09, , 14F
01/24 13:09, 14F
推
01/24 15:09, , 15F
01/24 15:09, 15F
→
01/24 15:10, , 16F
01/24 15:10, 16F
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
