合并 K 个排序数组

Question

我有 k 个排序数组，需要将它们合并为一个排序数组。我们假设 n 是所有输入数组中元素的总数并且 k=3。

public class Merge {

// Create a mergeklists() to merge 3 sorted arrays into one sorted array
// Input: 3 sorted arrays a1[], a2[], a3[]
// Output: one sorted array a[] that contains all the elements from input arrays

public static void merge3lists(int[] a1, int[] a2, int[] a3, int[] a)
{
    int i=0;
    int j=0;
    int h=0;
    int n = a1.length + a2.length + a3.length;
    for(int k;  a.length < n-1; k++){
        if(a1[i] < a2[j]){
            k = a1[i];
            i++;
        }
        else if(a2[j] < a3[h]){
            k = a2[j];
            j++;
        }
        else{
            k = a3[h];
            h++;
        }
    }



}   


public static void main(String[] args) {


    int[] l1 = {1,5,9,10,20};

    int[] l2 = {2,4,5,6,7,9,15};

    int[] l3 = {3,8,13,15,22};

    int[] newl = new int[l1.length+l2.length+l3.length];


    merge3lists(l1,l2,l3,newl);
    for(int i = 0; i< newl.length; i++)
    {
        System.out.print(newl[i]+ " ");
    }


}

}

我知道我使用的整数 (I、j 和 h) 正在搞乱这个问题，但我不认为我可以在比较所有数组时使用 i。我需要使用声明的数组 a，但我不确定在这种情况下如何引用它。

Answer 1

看起来像是一个激发引入数组数组的准备练习:)

为类似于列表的索引编号以避免混淆。

确定在当前索引处具有最小元素的列表。避免读取超出数组末尾的内容，因为这会导致异常。

接受这个元素并继续。

int i1=0;
int i2=0;
int i3=0;
int n = a1.length + a2.length + a3.length;
for( int k = 0;  k < n; k++) {
  int advance = 0;
  int value = Integer.MAX_VALUE;
  if (i1 < a1.length && a1[i1] <= value) {
    advance = 1;
    value = a1[i1]; 
  }
  if (i2 < a2.length && a2[i2] <= value) {
    advance = 2;
    value = a2[i2]; 
  }
  if (i3 < a3.length && a3[i3] <= value) {
    advance = 3;
    value = a3[i3]; 
  }
  a[k] = value;
  switch(advance) {
  case 1: i1++; break;
  case 2: i2++; break;
  case 3: i3++; break;
  }
}

Answer 2

要合并任意数量的数组 (k)，您需要使该方法使用可变参数。

最好让方法为您创建结果数组。

然后循环直到结果数组被填满。对于每次迭代，您从每个源数组中找到下一个值的最小值，并将其添加到结果数组，然后在您从中选择值的源数组中向前推进。

像这样：

public static int[] mergeArrays(int[]... arrays) {
    // Create result array
    int n = 0;
    for (int[] a : arrays)
        n += a.length;
    int[] result = new int[n];

    // Start at index 0 in each source array
    int[] idx = new int[arrays.length];

    // Merge source arrays into result array
    for (int i = 0; i < n; i++) {

        // Find smallest value
        int minJ = -1, minVal = 0;
        for (int j = 0; j < arrays.length; j++) {
            if (idx[j] < arrays[j].length) {
                int val = arrays[j][idx[j]];
                if (minJ == -1 || val < minVal) {
                    minJ = j;
                    minVal = val;
                }
            }
        }

        // Add to result array and step forward in appropriate source array
        result[i] = minVal;
        idx[minJ]++;
    }
    return result;
}

测试

int[] merged = mergeArrays(new int[] { 23, 39, 63, 68 },
                           new int[] { 11, 21, 76 },
                           new int[] {  5, 10, 37, 80 },
                           new int[] { 30, 49, 50, 94 },
                           new int[] { 13, 25, 48 });
System.out.println(Arrays.toString(merged));

输出

[5, 10, 11, 13, 21, 23, 25, 30, 37, 39, 48, 49, 50, 63, 68, 76, 80, 94]

Answer 3

更有效的算法是使用最小堆。

算法大致描述如下：

首先，构造一个大小为 k 的最小堆（在本例中，三个列表的大小为 3），采用每个列表中的最少元素。然后，您将从堆中删除最小元素（注意它来自哪个列表），将其添加到新构造的列表中，然后插入最初从中提取的同一列表中的下一个元素。

时间复杂度将从 O(n * k) 下降到 O(n * log(k))。其中 n 是最终排序列表中的元素总数。

https://cs.stackexchange.com/questions/12853/heap-give-an-on-lg-k-time-algorithm-to-merge-k-sorted-lists-into-one-so

合并 K 个排序数组

Merge K sorted arrays

java

sorting

algorithm

merge

mergesort