Объединить отсортированные массивы K размером n с помощью алгоритма слияния из mergeSort - PullRequest
Новая
       10

Объединить отсортированные массивы K размером n с помощью алгоритма слияния из mergeSort

0 голосов
/ 23 декабря 2018

Проблема: учитывая K отсортированных массивов размером N каждый, объедините их и напечатайте отсортированный вывод. 

Sample Input-1:

K = 3, N =  4

arr[][] = { {1, 3, 5, 7},

            {2, 4, 6, 8},

            {0, 9, 10, 11}} ;


Sample Output-1: 

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Я знаю, что есть способ решить эту проблему, используя очередь с приоритетами / мин, ноЯ хочу сделать это с помощью процедуры слияния от mergeSort.Идея кажется достаточно простой ... на каждой итерации объединять оставшиеся массивы в группы по два, так что число массивов уменьшается вдвое на каждой итерации.

Однако, если деление на два приводит к нечетному числу, этостановится проблематичным.Моя идея состоит в том, что всякий раз, когда деление пополам приводит к нечетному числу, мы заботимся о дополнительном массиве, объединяя его с массивом, сформированным из последнего слияния.

Код, который я имею до сих пор, приведен ниже.Однако это работает только в одном из 30 тестовых случаев: 

static int[] mergeArrays(int[][] arr) {
        int k = arr.length;
        int n = arr[0].length;
        if(k < 2){
            return arr[0];
        }

        boolean odd_k;
        if(k%2){
            odd_k = false;
        }
        else{
            odd_k = true;
        }

        while(k > 1){
            int o;
            if(odd_k){
                o = (k/2) + 1;
            }
            else{
                o = k/2;
            }
            int[][] out = new int[o][];

            for(int i=0; i < k; i = i + 2){
                int[] a;
                int[] b;
                if(odd_k && i == (k-1)){
                    b = arr[i];
                    b = out[i-1];
                }
                else{
                    a = arr[i];
                    b = arr[i+1];
                }
                out[i] = mergeTwo(a, b);
            }
            k = k/2;
            if(k % 2 == 0){
                odd_k = false;
            }
            else{
                odd_k = true;
            }

            arr = out;
        }
        return arr[0];

    }

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

Ответы [ 3 ]

0 голосов
/ 23 декабря 2018

Как вы говорите, вы объединили два массива одновременно.Поскольку это неэффективно, вы можете объединить все подмассивы одновременно.Что вам нужно сделать, это найти минимум для каждого подмассива и запомнить положение этого элемента.

Для этого мы можем использовать другой массив (скажем, curPos), чтобы запомнить текущую позицию 

 private int[] merge(int[][] arr) 
{
    int K = arr.length;
    int N = arr[0].length;

    /** array to keep track of non considered positions in subarrays **/
    int[] curPos = new int[K];

    /** final merged array **/
    int[] mergedArray = new int[K * N];
    int p = 0;

    while (p < K * N)
    {
        int min = Integer.MAX_VALUE;
        int minPos = -1;
        /** search for least element **/
        for (int i = 0; i < K; i++)
        {
            if (curPos[i] < N)
            {
                if (arr[i][curPos[i]] < min)
                {
                    min = arr[i][curPos[i]];
                    minPos = i;
                }
            }                
        }
        curPos[minPos]++;            
        mergedArray[p++] = min;
    }
    return mergedArray;
0 голосов
/ 24 декабря 2018

Вероятно, самый простой способ справиться с этим - использовать очередь массивов.Сначала добавьте все массивы в очередь.Затем удалите первые два массива из очереди, объедините их и добавьте полученный массив в очередь.Продолжайте делать это, пока в очереди не останется только один массив.Что-то вроде: 

for each array in list of arrays
    queue.push(array)

while queue.length > 1
    a1 = queue.pop()
    a2 = queue.pop()
    a3 = merge(a1, a2)
    queue.push(a3)

result = queue.pop()

Это немного упрощает ситуацию, и проблема «деления пополам» исчезает.

0 голосов
/ 23 декабря 2018

Мы можем сократить вашу mergeTwo реализацию, 

static int[] mergeTwo(int[] a, int[] b) {
    int[] c = new int[a.length + b.length];
    int i = 0, j = 0, k = 0; // declare and initialize on one line
    while (i < a.length && j < b.length) {
        if (a[i] <= b[j]) {
            c[k++] = a[i++]; // increment and assign
        } else {
            c[k++] = b[j++]; // increment and assign
        }
    }
    // No need for extra if(s)
    while (i < a.length) {
        c[k++] = a[i++];
    }
    while (j < b.length) {
        c[k++] = b[j++];
    }
    return c;
}

И затем мы можем исправить ваши mergeArrays и сократить это, начав с первой строки из int[][]а затем с помощью mergeTwo итеративно объединить массивы.Мол, 

static int[] mergeArrays(int[][] arr) {
    int[] t = arr[0];
    for (int i = 1; i < arr.length; i++) {
        t = mergeTwo(t, arr[i]);
    }
    return t;
}

Затем я проверил это с 

public static void main(String[] args) {
    int arr[][] = { { 1, 3, 5, 7 }, { 2, 4, 6, 8 }, { 0, 9, 10, 11 } };
    System.out.println(Arrays.toString(mergeArrays(arr)));
}

И я получил (как и ожидалось) 

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
...