«1. Введение
В этом уроке мы узнаем, как объединить два отсортированных массива в один отсортированный массив.
2. Проблема
Давайте разберемся в проблеме. У нас есть два отсортированных массива, и мы хотели бы объединить их в один.
3. Алгоритм
Когда мы анализируем проблему, довольно легко заметить, что мы можем решить эту проблему, используя операцию слияния сортировки слиянием.
Допустим, у нас есть два отсортированных массива foo и bar длины fooLength и barLength соответственно. Затем мы можем объявить другой объединенный массив размером fooLength + barLength.
Затем мы должны пройти оба массива в одном и том же цикле. Мы будем поддерживать текущее значение индекса для каждого, fooPosition и barPosition. На данной итерации нашего цикла мы берем любой массив, в индексе которого находится элемент с меньшим значением, и продвигаем этот индекс. Этот элемент займет следующую позицию в объединенном массиве.
Наконец, после того, как мы перенесли все элементы из одного массива, мы скопируем оставшиеся элементы из другого в объединенный массив.
Теперь давайте посмотрим на процесс в картинках, чтобы лучше понять алгоритм.
Шаг 1:
Начнем со сравнения элементов в обоих массивах и выберем меньший.
Затем мы увеличиваем позицию в первом массиве.
Шаг 2:
Здесь мы увеличиваем позицию во втором массиве и переходим к следующему элементу, который равен 8.
Шаг 3:
В конце этой итерации мы прошли все элементы первого массива.
Шаг 4:
На этом шаге мы просто копируем все оставшиеся элементы из второго массива в результат.
4. Реализация
Теперь давайте посмотрим, как это реализовать:
public static int[] merge(int[] foo, int[] bar) {
int fooLength = foo.length;
int barLength = bar.length;
int[] merged = new int[fooLength + barLength];
int fooPosition, barPosition, mergedPosition;
fooPosition = barPosition = mergedPosition = 0;
while(fooPosition < fooLength && barPosition < barLength) {
if (foo[fooPosition] < bar[barPosition]) {
merged[mergedPosition++] = foo[fooPosition++];
} else {
merged[mergedPosition++] = bar[barPosition++];
}
}
while (fooPosition < fooLength) {
merged[mergedPosition++] = foo[fooPosition++];
}
while (barPosition < barLength) {
merged[mergedPosition++] = bar[barPosition++];
}
return merged;
}
И давайте проведем небольшой тест:
@Test
public void givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray() {
int[] foo = { 3, 7 };
int[] bar = { 4, 8, 11 };
int[] merged = { 3, 4, 7, 8, 11 };
assertArrayEquals(merged, SortedArrays.merge(foo, bar));
}
5. Сложность
Проходим по обоим массивам и выбираем меньший элемент. В конце копируем остальные элементы из массива foo или bar. Таким образом, временная сложность становится O (fooLength + barLength). Мы использовали вспомогательный массив для получения результата. Таким образом, пространственная сложность также равна O (fooLength + barLength).
6. Заключение
В этом уроке мы научились объединять два отсортированных массива в один.
Как обычно, исходный код этого руководства можно найти на GitHub.