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

Question

Например, для целочисленного массива и его начальной позиции двух последовательных последовательностей, которые являются 'b1' и 'b2', кроме того, обеспечивается позиция 'last', которая указывает конечную позицию второй последовательности. От массива [b1] до массива [b2-1] и от массива [b2] до массива [last] оба в отдельности по порядку, как объединить их на месте , используя время O (n) и пространство O (1) стоимость?

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

Здесь 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);
    }
}

Answer 5

Хотя это невозможно полностью за O(n) время, у меня есть предложение сделать это быстрее, чем O(n^2).Я использую только O(1) пробел, который является временным в моем коде.Я уверен, что он должен работать лучше, чем 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;
    }

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