合并未排序数组的集合以查找公共元素

合并未排序数组的类型类型与下面的代码类似吗？合并未排序数组的集合以查找公共元素

Comparable [][] collections {colA, colB, colC};

搜索后，我找到了一种合并两个有序数组原始数据的方法。

public static int[] merge(int[] a, int[] b) { 

int[] answer = new int[a.length + b.length]; 
int i = 0, j = 0, k = 0; 
while (i < a.length && j < b.length) 
{ 
    if (a[i] < b[j]) 
    { 
     answer[k] = a[i]; 
     i++; 
    } 
    else 
    { 
     answer[k] = b[j]; 
     j++; 
    } 
    k++; 
} 

while (i < a.length) 
{ 
    answer[k] = a[i]; 
    i++; 
    k++; 
} 

while (j < b.length) 
{ 
    answer[k] = b[j]; 
    j++; 
    k++; 
} 

return answer;

}

这里，How to merge two sorted arrays into a sorted array?

假设我的K阵列（例如，A &乙...），和欲获得列表C（允许重复的项目）。我只想一次比较每个元素。即使我在内存方面妥协，也能获得更快的性能。

谢谢！

来源

2015-09-24 sag_dc

如果您有k排序的数组，并且您正在寻找合并它们，您可以构建一个堆（PriorityQueue），该堆在开始处由每个列表中的第一个元素填充。

然后，直到队列为空：

从队列
弹出的最低元素追加元素排序合并列表
添加到队列中的下一个元素的列表，弹出的元素属于（如果存在）。

这在O(nlogk)时间，其中n是元件的总数和k是列表的数目来完成。很容易显示这个解决方案是最优的，因为否则您可以对未排序列表进行排序，比Omega(nlogn)

来源

2015-09-24 18:03:52 amit

对我来说，似乎步骤2似乎是O（k），导致O（nK），因为队列中的元素没有排序。我错过了什么？ –

好方法，但我怀疑我们可以找到更好的。我的问题意味着每次在EQQueue中添加ekement时，我们必须找到k个未排序元素的最小值。（请阅读第1步而不是第2步。） –

@ A.S.H这是优先级队列/堆。它被分类以找到O（1）中的最小值，在O（logk） – amit

您可以使用基本上与您列出的完全相同的算法。效率是O（nk^2），所以它不是最优的，但它会很容易实现，因为你已经知道如何在k = 2的情况下做到这一点。

来源

2015-09-24 18:56:28 Orch

合并未排序数组的集合以查找公共元素

回答

相关问题