合併未排序數組的集合以查找公共元素

合併未排序數組的類型類型與下面的代碼類似嗎？合併未排序數組的集合以查找公共元素

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

合併未排序數組的集合以查找公共元素

回答

相關問題