合并K个排序的数组 [英] Merge K sorted arrays

问题描述

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

I am given k sorted arrays and need to merge them into one sorted array. We are assuming that n is the total number of elements in all the input arrays and that 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，但是在这种情况下我不确定如何引用它.

I know that the integers I am using (I,j,and h) are messing up the problem, but I don't think I can use i while comparing all the arrays. I need to use the declared array a, but I'm not sure how to reference it in this case.

推荐答案

看起来像是准备练习，以鼓励引入数组数组:)

Looks like a preparation exercise to motivate the introduction of array of arrays :)

编号类似于列表的索引，以避免混淆.

Number the indices analogous to the lists to avoid confusion.

标识在其当前索引处具有最小元素的列表.避免读取超出数组末尾的内容，否则会导致异常.

Identify the list with the smallest element at its current index. Avoid reading beyond the end of the array, as it will result in an exception.

接受此元素，然后继续.

Take this element and proceed.

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;
  }
}

这篇关于合并K个排序的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！