Сортировка 2 массивов

Question

Это вопрос интервью, поэтому применяются обычные ограничения.

Один массив имеет размер n и n элементов. Второй массив имеет размер n + m и m элементов. Оба массива отсортированы. Вопрос в том, чтобы переместить все n + m элементов во второй массив в отсортированном порядке. O (N) желательно.

Нет упоминания о невозможности использовать дополнительное пространство, но, судя по этому вопросу, похоже, что оно не позволяет использовать дополнительное пространство.

Мы можем одновременно пройтись по двум массивам (а-ля Merge Sort) и объединить их, но для этого потребуется дополнительный массив или дополнительная сложность перемещения существующих элементов на 1 (что будет означать O (N2)).

Обновление: Вот пример.

Массив 1: {2, 4, 6, 10}

Массив2: {21, 23, 25,,,,}

Ответ: {2, 4, 6, 10, 21, 23, 25}

Answer 1

Пройдите по ним в порядке убывания. O (2N), а не O (N ^ 2).

Answer 2

Нет никаких упоминаний о невозможности использования дополнительного пространства, но, судя по вопросу, это не дает дополнительного пространства.

Вам не нужно никакого- у вас есть n элементов в одном массиве и m элементов в другом.У вас также есть n+m место в другом.Он может четко вместить объединение двух массивов.

---

Как уже упоминалось в других ответах, все, что вам нужно, это:

1. Итерация по двум массивам, начиная сконец каждого
2. Сравните два текущих элемента из двух массивов
3. Запишите больший из двух в последнюю позицию во втором массиве (тот, у которого есть дополнительный пробел)
4. Перейдите к следующему элементу в массиве, из которого вы только что написали, и обратите внимание, что следующий больший элемент будет записан в позицию, предшествующую позиции, в которую вы только что написали, независимо от того, содержит ли он элемент или нет
5. Если у вас закончились элементы в первом массиве, все готово, поскольку элементы второго массива уже находятся на своем месте
6. Если вместо этого у вас закончились элементы во втором массиве, вы просто копируетевсе элементы от первого ко второму движутся к головке массива.

---

/**
 * Assumes both array are sorted in ascending order
 * Array a has length n and contains n elements
 * Array b has length m+n and contains m elements
 * The merged, sorted array will be returned in b
 */

public void merge(int [] a, int [] b)
{
    //b is the one with m+n space
    int indexA = a.length - 1; //points to last element in a
    int indexB = b.length - a.length - 1; //points to last element in b
    int writeTo = b.length - 1; //points to last free position

    while(indexA > -1 && indexB > -1)
    {
        if(a[indexA] > b[indexB])
        {
            b[writeTo--] = a[indexA--]
        }
        else
        {
            b[writeTo--] = b[indexB--];
        }
    }

    //are there any elements left-over in a?
    //any elements left-over in b will already be in their right place
    while(indexA > -1)
    {
        b[writeTo--] = a[indexA--];
    }
}

Answer 3

Пройдите по двум массивам одновременно, но с конца данных, а не с начала. Запишите отсортированные данные, начиная с конца большего массива. Вам никогда не нужно будет ничего смещать. Все данные, которые вы перезаписываете, уже будут записаны в новом месте в массиве ... O (m + n)