Объедините два отсортированных массива на месте в пространстве O (1)

Может кто-нибудь, пожалуйста, помогите мне понять алгоритм/код для этой проблемы

учитывая два целочисленных массива, отсортируйте их так, чтобы начальные числа помещались в первый массив, а оставшиеся числа - во второй массив. Например:

Input: ar1[ ] = {1, 5, 9, 10, 15, 20}

        ar2[] = {2, 3, 8, 13}

Output: ar1[ ] = {1, 2, 3, 5, 8, 9}

         ar2[] = {10, 13, 15, 20}

Код:

    void merge(int ar1[], int ar2[], int m, int n)
{
    // Iterate through all elements of ar2[] starting from
    // the last element
    for (int i=n-1; i>=0; i--)
    {
        //Find the smallest element greater than ar2[i]. Move all
        //   elements one position ahead till the smallest greater
        //   element is not found
        int j, last = ar1[m-1];
        for (j=m-1; j >= 0 && ar1[j] > ar2[i]; j--)
            ar1[j+1] = ar1[j];

        // If there was a greater element
        if (j != m-1)
        {
            ar1[j+1] = ar2[i];
            ar2[i] = last;
        }
    }
}

Я видел это решение на этом веб-сайте: http://www.geeksforgeeks.org/merge-two-sorted-arrays-o1-extra-space/


arrays sorting in-place
person Ajinkya Kale    schedule 28.03.2016    source источник
comment
Ваша ссылка, кажется, хорошо объясняет алгоритм. Если вы можете указать, что вы не поняли, это поможет вам лучше ориентироваться.   -  person Sendhilkumar Alalasundaram    schedule 28.03.2016
comment
Привет, я не понимаю сравнения между последним элементом ar2 и тем, как он помещается в нужное место. Что здесь рационального или инвариантного? Также не будет ли это через исключение arrayIndexOutOfBound в ar1[j+1] = ar[j] ? Заранее спасибо.   -  person Ajinkya Kale    schedule 28.03.2016
comment
Я думаю, что вы правы, предполагая, что в этом цикле будет нарушение прав доступа. Внешнего оператора if, охватывающего как цикл, так и следующий оператор if и проверяющего, больше ли крайний правый элемент, чем ar2[i] в ​​ar1, было бы достаточно для предотвращения этого нарушения.   -  person ilim    schedule 28.03.2016
comment
Привет @ilim, спасибо за объяснение. Однако давайте рассмотрим первую итерацию: где i = 3, j = 5 ar1[j] > ar2[i], т.е. 20 > 13 верно, и, следовательно, он войдет в цикл for. Теперь, поскольку j = 5, обновление ar1 [j+1] вызовет исключение.   -  person Ajinkya Kale    schedule 29.03.2016
comment
@AjinkyaKale О, я забыл добавить, что вы должны начать внутренний цикл с m-2, как только вы добавите оператор if, о котором я упоминал в комментарии выше. Что касается остальной части моего объяснения относительно предоставленного вами кода, вы можете обратиться к моему ответу ниже.   -  person ilim    schedule 29.03.2016

Ответы (2)


arrow_upward
2
arrow_downward

Интуиция

Для каждого элемента ar2[i] из ar2 (т.е. внутри внешнего цикла) в основном вы находите индекс j в ar1 таким образом, что все элементы ar1 в диапазоне [(j+1), (m-1)] больше, чем ar2[i]. Затем вы берете наименьший элемент в этом диапазоне и отбрасываете его из ar1 в ar2, а именно в ячейку с индексом i, где когда-то находилось значение в ar2[i] перед переносом в ar1.

Причиной переноса ar2[i] в ar1[j+1] является попытка собрать наименьшие m элементов в ar1, а остальные - в ar2. Вероятно, элегантная вещь, которую делает этот алгоритм, — это обход ar2 справа налево. Если вы помните, что и ar1, и ar2 отсортированы, переход справа налево в ar2 помогает достичь используя постоянное дополнительное пространство следующим образом.

Когда вы идете справа налево по ar2, вы сталкиваетесь с уменьшением или, по крайней мере, с невозрастанием значений в ar2[i]. Это означает, что вы найдете уменьшающиеся или не возрастающие значения ar1[m-1], чтобы заменить их. По сути, наименьшие элементы ar1[m-1] больше ar2[i] не будут увеличиваться, поскольку значение ar2[i] уменьшается при движении справа налево.

Следовательно, элементы, которые мы сбрасываем с ar1 на arr2 в каждой итерации внешнего цикла, также будут в невозрастающем или убывающем порядке, и мы будем помещать их в индексы в порядке убывания, сохраняя порядок ar2.

Инвариантный подход

Возможным, хотя и довольно неформальным инвариантом может быть то, что ar1 и ar2 будут сортироваться после каждой итерации, причем не более одного элемента ar2, скажем, ar2[i], для которого существует по крайней мере 1 ar1[k]>ar2[i], заменяется на элемент в ar1 таким образом, чтобы не нарушать порядок сортировки любого массива.

Изначально элементы упорядочены. После каждой итерации, если существует элемент меньше ar2[i] в ar1 с индексом j, весь диапазон больше ar2[i] сдвигается вправо на 1. ar2[i] помещается в ar1[j+1] так, чтобы не нарушался порядок ar1. Затем ранее последний элемент ar1, который больше не помещается в ar1, помещается в ar2[i].

Легко видеть, что порядок ar1 сохраняется на каждой итерации внешнего цикла. Приказ ar2 требует немного больше внимания.

Каждый раз, когда мы помещаем элемент ar2 в ar1, мы знаем, что ранее последний элемент ar1, который мы помещаем в ar2 (т.е. вместо ar2[i]), больше, чем ar2[i], поскольку он больше или равен ar1[j+1], который был больше, чем ar2[i]. (ar2[i] < ar1[j+1] <= last)

Кроме того, все ранее замененные элементы в ar2 (т. е. элементы справа от i-го индекса ar2) были заменены значениями last, которые были больше или равны значению last в текущей итерации, поскольку Изначально был заказан ar1.

Следовательно, после каждой итерации ar2 также остается упорядоченным, а после завершения алгоритма не существует элемента ar2[i] такого, что был бы элемент ar1[k] > ar2[i].

person ilim    schedule 28.03.2016
comment
Привет, @ilim большое спасибо, это точное объяснение. Ценю вашу помощь. - person Ajinkya Kale; 29.03.2016

arrow_upward

arrow_downward

person    schedule
comment
Публикация кода в качестве ответа не помогает. Пожалуйста, уточните свой ответ с некоторым описанием. - person coderpc; 05.04.2019