Как объединить два отсортированных целочисленных массива на месте с использованием O (n) времени и O (1) пространственной стоимости

Ответ 1

Это отнюдь не простая проблема. Это возможно, но редко делается на практике, потому что она намного сложнее стандартного слияния с использованием пространства N-царапин. Документ Хуанга и Лангстона существует с конца 80-х годов, хотя практические реализации на самом деле не появились до конца. Раньше статья Л. Трабба-Прадо в 1977 году значительно превосходила Хуанга и Лэнгстона, но мне мешает найти точный текст этой статьи; только ссылки изобилуют.

Отличная последующая публикация Асимптотически эффективное слияние на месте (1995) Geert, Katajainenb и Pasanen - это хороший охват нескольких алгоритмы и ссылки. Вклад Trabb-Prado в тему.

Ответ 2

Слияние Kronrod было первым опубликованным алгоритмом для этого. Это примерно так:

Разделите обе части массива на блоки размером k = sqrt (n). Сортируйте блоки, используя их первые элементы, в качестве основы для сравнения. Это можно сделать в sqrt (n) ^ 2 = O (n) путем сортировки сортировки. Ключевым свойством сортировки здесь является то, что он имеет постоянные перемещения на блок, поэтому только # сравнения являются квадратными.

После этой фазы для каждого элемента A[i] в массиве не более k-1 элементов "неправильно отсортированы" под ним, то есть элементы в позициях j < i, такие что A[j]>A[i]. Это (возможно) в ближайшем блоке ниже, который исходит от другой объединенной части. Обратите внимание, что первый элемент блока (и все остальные блоки ниже) уже правильно отсортированы относительно A[i] из-за того, что блоки сортируются по их первым элементам. Вот почему работает вторая фаза, т.е. Достигает полностью отсортированного массива:

Теперь объедините первый блок со вторым, затем вторым с третьим и т.д., используя последние 2 блока как временное пространство для вывода слияния. Это будет скремблировать содержимое последних двух блоков, но на последней фазе они (вместе с предыдущим блоком) могут быть отсортированы по типу выбора в sqrt (n) ^ 2 = O (n) времени.

Ответ 3

Есть такие вещи, как истинные слияния на месте, но они недостаточно прямолинейны, чтобы кто-то собирался самостоятельно изобретать их в середине интервью - на протяжении многих лет на нем были описаны описания сложных алгоритмов для этого, Одно из них - практическое объединение на месте, Хуан и Лангстон, CACM, март 1988 года. Отправной идеей для этого является разделение данных длины n на блоки размера sqrt (n) и использование одного блока, заполненного самыми большими элементами данных, чтобы обеспечить буферное пространство, используемое при объединении других. Введение в эту статью гласит:

"Для двух отсортированных списков, длина которых равна n, очевидным методам слияния в шагах O (n) также требуется линейное количество дополнительной памяти. С другой стороны, легко слить, используя только постоянное количество дополнительного пространства путем сортировки кучи, но при стоимости O (n log n) времени"

Следовательно, я утверждаю, что истинное слияние на месте может быть сделано, но неочевидно.

Ответ 4

Хотя это невозможно во время O(n), у меня есть предложение сделать это быстрее, чем O(n^2). Я использую только O(1) пробел, который является temp в моем коде. Я уверен, что он должен работать лучше, чем O(n^2).

private static int[] mergeSortedArrays(int[] a1, int[] a2) {
        int i = 0, j = 0;
        while (a1[i] != Integer.MIN_VALUE) {
            if (a1[i] > a2[j]) {
                int temp = a1[i];
                a1[i] = a2[j];
                a2[j] = temp;

                for (int k = 1; k < a2.length; k++) {
                    if (a2[k - 1] > a2[k]) {
                        temp = a2[k - 1];
                        a2[k - 1] = a2[k];
                        a2[k] = temp;
                    }
                }
            }
            i++;
        }
        while(j < a2.length){
            a1[i++] = a2[j++];
        }
        return a1;
    }

Ответ 5

Здесь O (n-1) Память (n + 1)

/**
 * Created by deian on 2016-12-22.
 * We just need track the two smallest numbers 
 */
public class Merge {
    public static void swap(int[] a, int i1, int i2) {
        int t = a[i1];
        a[i1] = a[i2];
        a[i2] = t;
    }

    public static void merge(int[] a) {
        // i1 and i2 - always point to the smallest known numbers
        // it would works as well with two m and n sized arrays 
        int i1 = 0;
        int i2 = a.length / 2;

        System.out.printf("    %s,      i(%d,%d)       \n", Arrays.toString(a), i1, i2);
        for (int di = 0; di < a.length - 1; di++) {
            int ni;
            int oi1 = i1; int oi2 = i2;
            if (a[i1] > a[i2]) {
                ni = i2; i2++;
                if (i2 >= a.length) { i2--; }
            } else {
                ni = i1; i1++;
                if (i1 >= i2) { i1 = di; }
            }
            if (di == i1) { i1 = ni; }
            swap(a, di, ni);
            System.out.printf("#%d: %s, i(%d,%d)s(%d>%d)i(%d,%d) \n", di + 1, Arrays.toString(a), oi1, oi2, ni, di, i1, i2);
        }
        System.out.printf("    %s\n", Arrays.toString(a));
    }

    public static void main(String[] args) {
//        int[] a = new int[]{1, 3, 6, 8, -5, -2, 3, 8};
//        int[] a = new int[]{1, 3, 6, 8, -5, 2, 3, 8};
//        int[] a = new int[]{1, 5, 6, 8, -5, 2, 3, 4};
//        int[] a = new int[]{1, 5, 6, 8, -5, -2, -1, 4};
//        int[] a = new int[]{ 1, 2, 3, 4, 5, 6, 7, 8};
//        int[] a = new int[]{5, 6, 7, 8, 1, 2, 3, 4};
        int[] a = new int[]{1, 3, 5, 7, 2, 4, 6, 8};
        merge(a);
    }
}

Ответ 6

Несколько часов назад у меня было интервью (с очень важной компанией), и меня спросили об этом. В Java есть ответ

public static void main(String[] args) {
    int A[] = { 1, 3, 5, 6, 9 };
    int B[] = new int[12];
    B[0] = 3;
    B[1] = 6;
    B[2] = 8;
    B[3] = 10;
    B[4] = 11;
    B[5] = 13;
    B[6] = 15;
    mergeInB(A, B, 7);
    for (int n : B)
        System.out.print(n + " ");
}



 /**
 * @param a
 * @param b - it will be modified
 * @param j = length of b
 */
public static void mergeInB(int[] a, int[] b, int j) {
    int i = a.length - 1, k;
    j --;
    for (k = b.length-1; k >= 0; k--) {
         if (i >= 0 && j >= 0) {
             if (a[i] > b[j]) {
                 b[k] = a[i];
                 i --;
             }
             else 
              {
                 b[k] = b[j];
                 j --;
             }               
         }
         else break;
    }

    while(i>=0 && k >=0) {
         b[k] = a[i];
         k --;
         i --;
    }

    while(j>= 0 && k >=0) {
         b[k] = b[j];
         j--;
         k--;
     }
}