Об этом меня спросили в интервью, и вот решение, которое я предоставил:
public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
{
if (a[i] < b[j])
{
answer[k] = a[i];
i++;
}
else
{
answer[k] = b[j];
j++;
}
k++;
}
while (i < a.length)
{
answer[k] = a[i];
i++;
k++;
}
while (j < b.length)
{
answer[k] = b[j];
j++;
k++;
}
return answer;
}
Есть ли более эффективный способ сделать это?
Изменить: Исправлены методы длины.
while (i < a.length && j < b.length) answer[k++] = a[i] < b[j] ? a[i++] : b[j++];
Java Спецификация языка: Условный оператор? : .Ответы:
Незначительное улучшение, но после основного цикла вы можете использовать
System.arraycopy
для копирования хвоста любого входного массива, когда доберетесь до конца другого. Это не изменитO(n)
характеристики производительности вашего решения.источник
Это немного более компактно, но точно так же!
источник
Я удивлен, что никто не упомянул эту гораздо более классную, эффективную и компактную реализацию:
Точки интересов
System.arraycopy
выиграют, потому что внутренне это можно сделать с помощью одной инструкции сборки x86.a[i] >= b[j]
вместоa[i] > b[j]
. Это гарантирует «стабильность», которая определяется, когда элементы a и b равны, нам нужны элементы от a до b.источник
j < 0
,b
уже исчерпан, поэтому мы продолжаем добавлять оставшиесяa
элементы вanswer
массивЛюбые улучшения, которые можно было бы сделать, были бы микрооптимизациями, а общий алгоритм правилен.
источник
System.arrayCopy()
тупо быстр, поскольку используетmemcpy
вызовы, оптимизированные для процессора . Так что есть возможность улучшить производительность путем копирования фрагментов. Также есть возможность бинарного поиска границ.Это решение также очень похоже на другие публикации, за исключением того, что оно использует System.arrayCopy для копирования оставшихся элементов массива.
источник
Вот обновленная функция. Он удаляет дубликаты, надеюсь, кто-то найдет это пригодным для использования:
источник
Это можно сделать в 4 заявления, как показано ниже
источник
sort
функция не может использовать себя в качестве метода сортировки. Это было бы бесконечной регрессией вместо рекурсии. Также другая предпосылка заключается в том, что merge_array - это функция, которая реализует сортировку. Таким образом, этот ответ непригоден в наиболее вероятном контексте.Я должен был написать это в JavaScript, вот оно:
источник
Apache collection поддерживает метод сортировки начиная с версии 4; Вы можете сделать это, используя
collate
метод в:Вот цитата из Javadoc:
Не изобретай велосипед! Ссылка на документ: http://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/CollectionUtils.html
источник
GallopSearch Merge: O (log (n) * log (i)), а не O (n)
Я пошел дальше и реализовал предложение серой бороды в комментариях. Главным образом потому, что мне нужна высокоэффективная критическая версия этого кода.
Это должен быть наиболее эффективный способ сделать это с временной сложностью O (log (n) * log (i)), а не O (n). И в худшем случае временная сложность O (n). Если ваши массивы клочковатые и содержат длинные цепочки значений, это затмит любой другой способ сделать это, иначе это будет просто лучше, чем они.
Он имеет два значения чтения на концах массива объединения и значение записи в массиве результатов. После того, как выясняется, какое из конечных значений меньше, он делает скачок в этом массиве. 1, 2, 4, 8, 16, 32 и т. Д. Когда он находит диапазон, в котором значение чтения другого массива больше. Он выполняет двоичный поиск в этом диапазоне (сокращает диапазон пополам, ищет правильную половину, повторяет до одного значения). Затем массив копирует эти значения в позицию записи. Помните, что копия по необходимости перемещается так, что не может перезаписывать одинаковые значения из любого массива чтения (что означает, что массив записи и массив чтения могут быть одинаковыми). Затем он выполняет ту же операцию для другого массива, который, как теперь известно, меньше нового значения чтения другого массива.
Это должен быть самый эффективный способ сделать это.
У некоторых ответов была возможность удаления дубликатов. Это потребует алгоритма O (n), потому что вы должны сравнить каждый элемент. Так что вот для этого отдельная вещь, которая будет применяться после факта. Вы не можете просматривать несколько записей, если вам нужно просмотреть все из них, хотя вы могли бы просматривать дубликаты, если их было много.
Обновление: предыдущий ответ, не ужасный код, но явно уступает вышеуказанному.
Еще одна ненужная гипероптимизация. Он не только запускает arraycopy для конечных битов, но и для начала. Обработка любого вводного непересекающегося в O (log (n)) двоичного поиска в данных. O (log (n) + n) - это O (n), и в некоторых случаях эффект будет довольно выраженным, особенно в тех случаях, когда вообще нет перекрытия между объединяющимися массивами.
источник
That is totally what the implemented Arrays.sort does
( То есть : из первой редакции вашего ответа - или - из моего комментария 19 февраля?) - вы не можете найти ни в SunDK JDK 8: на какую реализациюArrays.sort
вы ссылаетесь?Вот сокращенная форма, написанная на javascript:
источник
источник
a[mid+1 .. hi]
вaux
течение?Я думаю, что введение списка пропусков для большего отсортированного массива может уменьшить количество сравнений и ускорить процесс копирования в третий массив. Это может быть хорошо, если массив слишком велик.
источник
источник
источник
for (int i, j, k = i = j = 0 ; k < c.length ; ) c[k++] = b.length <= j || i < a.length && a[i] < b[j] ? a[i++] : b[j++];
. Чем он отличается от ответа Эндрю 2014 года ?Алгоритм может быть улучшен многими способами. Например, разумно проверить, если
a[m-1]<b[0]
илиb[n-1]<a[0]
. В любом из этих случаев нет необходимости делать больше сравнений. Алгоритм может просто скопировать исходные массивы в полученный в правильном порядке.Более сложные усовершенствования могут включать в себя поиск чередующихся частей и запуск алгоритма слияния только для них. Это может сэкономить много времени, когда размеры объединенных массивов различаются в десятки раз.
источник
Эта проблема связана с алгоритмом сортировки слиянием, в котором два отсортированных подмассива объединяются в один отсортированный подмассив. Книга CLRS дает пример алгоритма и устраняет необходимость проверки достижения конца путем добавления значения часового (что сравнивается и «больше, чем любое другое значение») в конец каждого массива.
Я написал это на Python, но он также должен хорошо переводиться на Java:
источник
Вы можете использовать 2 потока для заполнения результирующего массива, один спереди, один сзади.
Это может работать без какой-либо синхронизации в случае чисел, например, если каждый поток вставляет половину значений.
источник
источник
источник
источник
Мой любимый язык программирования - JavaScript
источник
Может быть, использовать System.arraycopy
источник
Выход:
1, 2, 3, 4, 5, 6, 8, 9, 10, 100, 999, 1001,
источник
arr2
нетind2
, ноtemp
.Вы можете использовать троичные операторы, чтобы сделать код немного более компактным
источник
Просто немного отличается от оригинального решения
источник
Чтобы пометить два отсортированных массива за O (m + n) сложность времени, используйте подход ниже только с одним циклом. m и n - длина первого массива и второго массива.
источник
источник
Поскольку вопрос не предполагает какого-либо конкретного языка. Вот решение в Python. Предполагая, что массивы уже отсортированы.
Подход 1 - использование массивов NumPy: импорт NUMPY
Подход 2 - Использование списка, при условии, что списки отсортированы.
источник
Since the question doesn't assume any specific language
с 2011/5/11/19: 43 он помечен как Java ..sort()
какO(n log n)
в лучшем случаеВот моя реализация Java, которая удаляет дубликаты.
источник