我不清楚这个问题是不是应该在此版发问，因为有点像演算法或资料结构的问题 如果不妥或违反板规我会立刻删文! 问题是这样的： 我现在有两个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)