[問題] 關於set的merge

[flipsydee (原來是宅男)]

我不清楚這個問題是不是應該在此版發問，因為有點像演算法或資料結構的問題

如果不妥或違反板規我會立刻刪文!


問題是這樣的：

我現在有兩個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)
→ jokester:"合併"是哪種操作? intersection? union?
→ jokester:這是c代碼嗎? 怎會返回一個棧上的指針@@
是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)
推 jokester:哈@@ 抱歉我看太快, 沒有看到是虛擬碼
→ jokester:可以把AB分別排序 再匯合到C
推 jokester:兩次排序和一次merge, 結果會有O(MlogM)
推 suhorng:這個merge沒處理重複的狀況...
我又寫了一個...網路上搜尋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)
推 suhorng:因為比較多是不限定用什麼實作set吧
→ suhorng:例如用hash table代表set, 然後去討論各種
→ suhorng:操作的時間複雜度之類.
推 singlovesong:沒仔細看題目 不過set union不是課
→ singlovesong:本裡面有最佳算法嗎
→ singlovesong:path compression union by rank?
那個好像是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)
推 yvb:test1.c 的 radixsort(), 註解的 O(1) 是??
→ yvb:test2.c 若 M=100, N=10, A[0]=1000 會怎樣?
推 singlovesong:最慘就Mlog(M)吧, balanced tree硬做
→ singlovesong:題目這樣出應該是要想Mlog(N)的解