我不清楚這個問題是不是應該在此版發問，因為有點像演算法或資料結構的問題 如果不妥或違反板規我會立刻刪文! 問題是這樣的： 我現在有兩個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) 是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) 我又寫了一個...網路上搜尋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) 那個好像是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)