Как объединить два отсортированных массива в сортированный массив? [закрытый]
Это было предложено мне в интервью, и это решение я предоставил:
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;
}
существует ли более эффективный способ сделать это?
изменить: исправлены методы длины.
30 ответов:
незначительное улучшение, но после основного цикла, вы можете использовать
System.arraycopyчтобы скопировать хвост любого входного массива, когда вы доберетесь до конца другого. Это не изменитO(n)характеристики производительности вашего решения, однако.
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) answer[k++] = a[i] < b[j] ? a[i++] : b[j++]; while (i < a.length) answer[k++] = a[i++]; while (j < b.length) answer[k++] = b[j++]; return answer; }немного компактнее, но точно так же!
Я удивлен, что никто не упомянул об этом гораздо более крутой, эффективной и компактной реализации:
public static int[] merge(int[] a, int[] b) { int[] answer = new int[a.length + b.length]; int i = a.length - 1, j = b.length - 1, k = answer.length; while (k > 0) answer[--k] = (j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--]; return answer; }достопримечательности
- обратите внимание, что он выполняет такое же или меньшее количество операций, как и любой другой O (n) алгоритм, но в буквальном смысле одного оператора в одном цикле while!
- если два массива имеют приблизительно одинаковый размер, то константа для O (n) одинакова. Однако если массивы действительно несбалансированы, то версии с
System.arraycopyпобедит, потому что внутренне он может сделать это с помощью одной инструкции ассемблера x86.- обратите внимание
a[i] >= b[j]вместоa[i] > b[j]. Это гарантирует "стабильность", которая определяется как когда элементы a и b равны, мы хотим, чтобы элементы от a до b.
Это решение также очень похоже на другие сообщения, за исключением того, что оно использует систему.arrayCopy для копирования оставшихся элементов массива.
private static int[] sortedArrayMerge(int a[], int b[]) { int result[] = new int[a.length +b.length]; int i =0; int j = 0;int k = 0; while(i<a.length && j <b.length) { if(a[i]<b[j]) { result[k++] = a[i]; i++; } else { result[k++] = b[j]; j++; } } System.arraycopy(a, i, result, k, (a.length -i)); System.arraycopy(b, j, result, k, (b.length -j)); return result; }
здесь обновляется функция. Он удаляет дубликаты, надеюсь, кто-то найдет это полезным:
public static long[] merge2SortedAndRemoveDublicates(long[] a, long[] b) { long[] answer = new long[a.length + b.length]; int i = 0, j = 0, k = 0; long tmp; while (i < a.length && j < b.length) { tmp = a[i] < b[j] ? a[i++] : b[j++]; for ( ; i < a.length && a[i] == tmp; i++); for ( ; j < b.length && b[j] == tmp; j++); answer[k++] = tmp; } while (i < a.length) { tmp = a[i++]; for ( ; i < a.length && a[i] == tmp; i++); answer[k++] = tmp; } while (j < b.length) { tmp = b[j++]; for ( ; j < b.length && b[j] == tmp; j++); answer[k++] = tmp; } return Arrays.copyOf(answer, k); }
Это может быть сделано в 4 заявления, как показано ниже
int a[] = {10, 20, 30}; int b[]= {9, 14, 11}; int res[]=new int[a.legth+b.length]; System.arraycopy(a,0, res, 0, a.length); System.arraycopy(b,0,res,a.length, b.length); Array.sort(res)
Я должен был написать его на javascript, вот он:
function merge(a, b) { var result = []; var ai = 0; var bi = 0; while (true) { if ( ai < a.length && bi < b.length) { if (a[ai] < b[bi]) { result.push(a[ai]); ai++; } else if (a[ai] > b[bi]) { result.push(b[bi]); bi++; } else { result.push(a[ai]); result.push(b[bi]); ai++; bi++; } } else if (ai < a.length) { result.push.apply(result, a.slice(ai, a.length)); break; } else if (bi < b.length) { result.push.apply(result, b.slice(bi, b.length)); break; } else { break; } } return result; }
Apache collections поддерживает метод collate начиная с версии 4; Вы можете сделать это с помощью
collateметод в:org.apache.commons.collections4.CollectionUtilsвот цитата из javadoc:
collate(Iterable<? extends O> a, Iterable<? extends O> b, Comparator<? super O> c)слияние двух отсортированных коллекций,
aиb, в единый, отсортировать список таким образом, чтобы упорядочение элементов по Компаратор С сохраняется.не изобретайте заново колесо! Документ ссылка: http://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/CollectionUtils.html
вот сокращенная форма, написанная на javascript:
function sort( a1, a2 ) { var i = 0 , j = 0 , l1 = a1.length , l2 = a2.length , a = []; while( i < l1 && j < l2 ) { a1[i] < a2[j] ? (a.push(a1[i]), i++) : (a.push( a2[j]), j++); } i < l1 && ( a = a.concat( a1.splice(i) )); j < l2 && ( a = a.concat( a2.splice(j) )); return a; }
GallopSearch Слияние:O (log (n)*log(i)) а не O (n)
Я пошел вперед и реализовал предложение седой бороды в комментариях. В основном потому, что мне нужна была высокоэффективная критически важная версия этого кода.
- код использует gallopSearch, который является O (log (i)), где i - это расстояние от текущего индекса соответствующий индекс существует.
- код использует binarySearch для После галоп поиска имеет определены правильно, дальность. Поскольку галоп ограничивался этим меньшим диапазон результирующий binarySearch также O (log (i))
- галоп и слияние выполняются в обратном направлении. Это не кажется миссия критическая, но она позволяет на месте слияния массивов. Если один из ваши массивы имеет достаточно места для хранения значений результатов, вы можете просто используйте его в качестве объединяющего массива и массив результатов. В этом случае необходимо указать допустимый диапазон в пределах массива.
- это не в этом случае требуется выделение памяти (большая экономия в критических операциях). Он просто гарантирует, что он не делает и не может перезаписать любые необработанные значения (которые могут быть сделаны только в обратном направлении). По сути, вы используете один и тот же массив для обоих входов и результатов. Он не будет страдать от каких-либо вредных последствий.
- я последовательно использовал целое.сравните (), чтобы это можно было переключить для других целей.
- есть некоторый шанс, что я, возможно, немного поглупел и не использовал информацию I уже доказано ранее. Например, двоичный поиск в диапазоне двух значений, для которых значение уже было проверено. Также может быть лучший способ указать основной цикл, значение flipping c не потребуется, если они будут объединены в две операции последовательно. Поскольку вы знаете, что будете делать одно, то и другое каждый раз. Там есть место для полировки.
это должно быть наиболее эффективным способом сделать это, с временной сложностью O (log (n)*log(i)) а не O(n). И наихудшая временная сложность O (n). Если ваши массивы неуклюжи и имеют длинные строки значений вместе, это затмит любой другой способ сделать это, иначе это будет просто лучше, чем они.
он имеет два значения чтения на концах массива слияния и значение записи в массиве результатов. После выяснения, какое конечное значение меньше, он выполняет поиск галопа в этом массиве. 1, 2, 4, 8, 16, 32, и т. д. Когда он находит в другой массив читать значение больше. Он выполняет двоичный поиск в этом диапазоне (сокращает диапазон пополам, ищет правильную половину, повторяет до одного значения). Затем массив копирует эти значения в позицию записи. Имея в виду, что копия по необходимости перемещается таким образом, что она не может перезаписать одни и те же значения из любого массива чтения (что означает, что массив записи и массив чтения могут быть одинаковыми). Затем он выполняет ту же операцию для другого массива, который теперь известен как меньше, чем новое значение чтения другой массив.
static public int gallopSearch(int current, int[] array, int v) { int d = 1; int seek = current - d; int prevIteration = seek; while (seek > 0) { if (Integer.compare(array[seek], v) <= 0) { break; } prevIteration = seek; d <<= 1; seek = current - d; if (seek < 0) { seek = 0; } } if (prevIteration != seek) { seek = binarySearch(array, seek, prevIteration, v); seek = seek >= 0 ? seek : ~seek; } return seek; } static public int binarySearch(int[] list, int fromIndex, int toIndex, int v) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; int midVal = list[mid]; int cmp = Integer.compare(midVal, v); if (cmp < 0) { low = mid + 1; } else if (cmp > 0) { high = mid - 1; } else { return mid;// key found } } return -(low + 1);// key not found. } static public int[] sortedArrayMerge(int[] a, int[] b) { return sortedArrayMerge(null, a, a.length, b, b.length); } static public int[] sortedArrayMerge(int[] results, int[] a, int aRead, int b[], int bRead) { int write = aRead + bRead, length, gallopPos; if ((results == null) || (results.length < write)) { results = new int[write]; } if (aRead > 0 && bRead > 0) { int c = Integer.compare(a[aRead - 1], b[bRead - 1]); while (aRead > 0 && bRead > 0) { switch (c) { default: gallopPos = gallopSearch(aRead, a, b[bRead-1]); length = (aRead - gallopPos); write -= length; aRead = gallopPos; System.arraycopy(a, gallopPos--, results, write, length); c = -1; break; case -1: gallopPos = gallopSearch(bRead, b, a[aRead-1]); length = (bRead - gallopPos); write -= length; bRead = gallopPos; System.arraycopy(b, gallopPos--, results, write, length); c = 1; break; } } } if (bRead > 0) { if (b != results) { System.arraycopy(b, 0, results, 0, bRead); } } else if (aRead > 0) { if (a != results) { System.arraycopy(a, 0, results, 0, aRead); } } return results; }это должно быть наиболее эффективным способом сделать это.
некоторые ответы имели дубликат удалить способность. Для этого потребуется алгоритм O(n), потому что вы должны фактически сравнить каждый элемент. Итак, вот автономный для этого, который будет применяться после факта. Вы не можете проскакать через несколько записей полностью, если вам нужно посмотреть на все из них, хотя вы могли бы проскакать через дубликаты, если бы у вас было много их.
static public int removeDuplicates(int[] list, int size) { int write = 1; for (int read = 1; read < size; read++) { if (list[read] == list[read - 1]) { continue; } list[write++] = list[read]; } return write; }
обновление: предыдущий ответ, не ужасный код, но явно уступает выше.
еще одна ненужная гипер-оптимизация. Он не только вызывает arraycopy для конечных битов, но и для начала. Обработка любого вводного неперекрывания в O(log (n)) с помощью binarySearch в данные. O (log (n) + n) - Это O (n), и в некоторых случаях эффект будет довольно выраженным, особенно там, где нет перекрытия между объединяющимися массивами все.
private static int binarySearch(int[] array, int low, int high, int v) { high = high - 1; while (low <= high) { int mid = (low + high) >>> 1; int midVal = array[mid]; if (midVal > v) low = mid + 1; else if (midVal < v) high = mid - 1; else return mid; // key found } return low;//traditionally, -(low + 1); // key not found. } private static int[] sortedArrayMerge(int a[], int b[]) { int result[] = new int[a.length + b.length]; int k, i = 0, j = 0; if (a[0] > b[0]) { k = i = binarySearch(b, 0, b.length, a[0]); System.arraycopy(b, 0, result, 0, i); } else { k = j = binarySearch(a, 0, a.length, b[0]); System.arraycopy(a, 0, result, 0, j); } while (i < a.length && j < b.length) { result[k++] = (a[i] < b[j]) ? a[i++] : b[j++]; } if (j < b.length) { System.arraycopy(b, j, result, k, (b.length - j)); } else { System.arraycopy(a, i, result, k, (a.length - i)); } return result; }
public class Merge { // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi] public static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) { // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays assert isSorted(a, lo, mid); assert isSorted(a, mid+1, hi); // copy to aux[] for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } // merge back to a[] int i = lo, j = mid+1; for (int k = lo; k <= hi; k++) { if (i > mid) a[k] = aux[j++]; else if (j > hi) a[k] = aux[i++]; else if (less(aux[j], aux[i])) a[k] = aux[j++]; else a[k] = aux[i++]; } // postcondition: a[lo .. hi] is sorted assert isSorted(a, lo, hi); } // mergesort a[lo..hi] using auxiliary array aux[lo..hi] private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, aux, lo, mid); sort(a, aux, mid + 1, hi); merge(a, aux, lo, mid, hi); } public static void sort(Comparable[] a) { Comparable[] aux = new Comparable[a.length]; sort(a, aux, 0, a.length-1); assert isSorted(a); } /*********************************************************************** * Helper sorting functions ***********************************************************************/ // is v < w ? private static boolean less(Comparable v, Comparable w) { return (v.compareTo(w) < 0); } // exchange a[i] and a[j] private static void exch(Object[] a, int i, int j) { Object swap = a[i]; a[i] = a[j]; a[j] = swap; } /*********************************************************************** * Check if array is sorted - useful for debugging ***********************************************************************/ private static boolean isSorted(Comparable[] a) { return isSorted(a, 0, a.length - 1); } private static boolean isSorted(Comparable[] a, int lo, int hi) { for (int i = lo + 1; i <= hi; i++) if (less(a[i], a[i-1])) return false; return true; } /*********************************************************************** * Index mergesort ***********************************************************************/ // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi] private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) { // copy to aux[] for (int k = lo; k <= hi; k++) { aux[k] = index[k]; } // merge back to a[] int i = lo, j = mid+1; for (int k = lo; k <= hi; k++) { if (i > mid) index[k] = aux[j++]; else if (j > hi) index[k] = aux[i++]; else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++]; else index[k] = aux[i++]; } } // return a permutation that gives the elements in a[] in ascending order // do not change the original array a[] public static int[] indexSort(Comparable[] a) { int N = a.length; int[] index = new int[N]; for (int i = 0; i < N; i++) index[i] = i; int[] aux = new int[N]; sort(a, index, aux, 0, N-1); return index; } // mergesort a[lo..hi] using auxiliary array aux[lo..hi] private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, index, aux, lo, mid); sort(a, index, aux, mid + 1, hi); merge(a, index, aux, lo, mid, hi); } // print array to standard output private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.println(a[i]); } } // Read strings from standard input, sort them, and print. public static void main(String[] args) { String[] a = StdIn.readStrings(); Merge.sort(a); show(a); } }
Я думаю, что введение списка пропусков для большего отсортированного массива может уменьшить количество сравнений и ускорить процесс копирования в третий массив. Это может быть хорошо, если массив слишком большой.
public int[] merge(int[] a, int[] b) { int[] result = new int[a.length + b.length]; int aIndex, bIndex = 0; for (int i = 0; i < result.length; i++) { if (aIndex < a.length && bIndex < b.length) { if (a[aIndex] < b[bIndex]) { result[i] = a[aIndex]; aIndex++; } else { result[i] = b[bIndex]; bIndex++; } } else if (aIndex < a.length) { result[i] = a[aIndex]; aIndex++; } else { result[i] = b[bIndex]; bIndex++; } } return result; }
public static int[] merge(int[] a, int[] b) { int[] mergedArray = new int[(a.length + b.length)]; int i = 0, j = 0; int mergedArrayIndex = 0; for (; i < a.length || j < b.length;) { if (i < a.length && j < b.length) { if (a[i] < b[j]) { mergedArray[mergedArrayIndex] = a[i]; i++; } else { mergedArray[mergedArrayIndex] = b[j]; j++; } } else if (i < a.length) { mergedArray[mergedArrayIndex] = a[i]; i++; } else if (j < b.length) { mergedArray[mergedArrayIndex] = b[j]; j++; } mergedArrayIndex++; } return mergedArray; }
алгоритм может быть улучшен во многих отношениях. Например, разумно проверить, если
a[m-1]<b[0]илиb[n-1]<a[0]. В любом из этих случаев нет необходимости проводить дополнительные сравнения. Алгоритм может просто скопировать исходные массивы в результирующем в правильном порядке.более сложные усовершенствования могут включать поиск перемежающихся частей и запуск алгоритма слияния только для них. Это может сэкономить много времени, когда размеры Объединенных массивов отличаются в десятки раз.
эта проблема связана с алгоритмом mergesort, в котором два отсортированных суб-массива объединяются в один отсортированный суб-массив. Элемент CLRS книга дает пример алгоритма и очищает необходимость проверки, если конец был достигнут путем добавления значения sentinel (что-то, что сравнивает и "больше, чем любое другое значение") в конец каждого массива.
Я написал это на Python, но он должен хорошо переводить на Java тоже:
def func(a, b): class sentinel(object): def __lt__(*_): return False ax, bx, c = a[:] + [sentinel()], b[:] + [sentinel()], [] i, j = 0, 0 for k in range(len(a) + len(b)): if ax[i] < bx[j]: c.append(ax[i]) i += 1 else: c.append(bx[j]) j += 1 return c
вы можете использовать 2 потока для заполнения результирующего массива, один спереди, один сзади.
Это может работать без какой-либо синхронизации в случае чисел, например, если каждый поток вставляет половина значений.
//How to merge two sorted arrays into a sorted array without duplicates? //simple C Coding #include <stdio.h> #include <stdlib.h> #include <string.h> main() { int InputArray1[] ={1,4,5,7,8,9,12,13,14,17,40}; int InputArray2[] ={4,5,11,14,15,17,18,19,112,122,122,122,122}; int n=10; int OutputArray[30]; int i=0,j=0,k=0; //k=OutputArray while(i<11 && j<13) { if(InputArray1[i]<InputArray2[j]) { if (k == 0 || InputArray1[i]!= OutputArray[k-1]) { OutputArray[k++] = InputArray1[i]; } i=i+1; } else if(InputArray1[i]>InputArray2[j]) { if (k == 0 || InputArray2[j]!= OutputArray[k-1]) { OutputArray[k++] = InputArray2[j]; } j=j+1; } else { if (k == 0 || InputArray1[i]!= OutputArray[k-1]) { OutputArray[k++] = InputArray1[i]; } i=i+1; j=j+1; } }; while(i<11) { if(InputArray1[i]!= OutputArray[k-1]) OutputArray[k++] = InputArray1[i++]; else i++; } while(j<13) { if(InputArray2[j]!= OutputArray[k-1]) OutputArray[k++] = InputArray2[j++]; else j++; } for(i=0; i<k; i++) { printf("sorted data:%d\n",OutputArray[i]); }; }
public static int[] merge(int[] listA, int[] listB) { int[] mergedList = new int[ listA.length + listB.length]; int i = 0; // Counter for listA int j = 0; // Counter for listB int k = 0; // Counter for mergedList while (true) { if (i >= listA.length && j >= listB.length) { break; } if (i < listA.length && j < listB.length) { // If both counters are valid. if (listA[i] <= listB[j]) { mergedList[k] = listA[i]; k++; i++; } else { mergedList[k] = listB[j]; k++; j++; } } else if (i < listA.length && j >= listB.length) { // If only A's counter is valid. mergedList[k] = listA[i]; k++; i++; } else if (i <= listA.length && j < listB.length) { // If only B's counter is valid mergedList[k] = listB[j]; k++; j++; } } return mergedList; }
var arrCombo = function(arr1, arr2){ return arr1.concat(arr2).sort(function(x, y) { return x - y; }); };
мой любимый язык программирования JavaScript
function mergeSortedArrays(a, b){ var result = []; var sI = 0; var lI = 0; var smallArr; var largeArr; var temp; if(typeof b[0] === 'undefined' || a[0]<b[0]){ smallArr = a; largeArr = b; } else{ smallArr = b; largeArr = a; } while(typeof smallArr[sI] !== 'undefined'){ result.push(smallArr[sI]); sI++; if(smallArr[sI]>largeArr[lI] || typeof smallArr[sI] === 'undefined'){ temp = smallArr; smallArr = largeArr; largeArr = temp; temp = sI; sI = lI; lI = temp; } } return result; }
возможно использовать систему.arraycopy
public static byte[] merge(byte[] first, byte[] second){ int len = first.length + second.length; byte[] full = new byte[len]; System.arraycopy(first, 0, full, 0, first.length); System.arraycopy(second, 0, full, first.length, second.length); return full; }
public static void main(String[] args) { int[] arr1 = {2,4,6,8,10,999}; int[] arr2 = {1,3,5,9,100,1001}; int[] arr3 = new int[arr1.length + arr2.length]; int temp = 0; for (int i = 0; i < (arr3.length); i++) { if(temp == arr2.length){ arr3[i] = arr1[i-temp]; } else if (((i-temp)<(arr1.length)) && (arr1[i-temp] < arr2[temp])){ arr3[i] = arr1[i-temp]; } else{ arr3[i] = arr2[temp]; temp++; } } for (int i : arr3) { System.out.print(i + ", "); } }вывод :
1, 2, 3, 4, 5, 6, 8, 9, 10, 100, 999, 1001,
вы можете использовать тернарные операторы для того, чтобы сделать код немного более компактным
public static int[] mergeArrays(int[] a1, int[] a2) { int[] res = new int[a1.length + a2.length]; int i = 0, j = 0; while (i < a1.length && j < a2.length) { res[i + j] = a1[i] < a2[j] ? a1[i++] : a2[j++]; } while (i < a1.length) { res[i + j] = a1[i++]; } while (j < a2.length) { res[i + j] = a2[j++]; } return res; }
public static int[] mergeSorted(int[] left, int[] right) { System.out.println("merging " + Arrays.toString(left) + " and " + Arrays.toString(right)); int[] merged = new int[left.length + right.length]; int nextIndexLeft = 0; int nextIndexRight = 0; for (int i = 0; i < merged.length; i++) { if (nextIndexLeft >= left.length) { System.arraycopy(right, nextIndexRight, merged, i, right.length - nextIndexRight); break; } if (nextIndexRight >= right.length) { System.arraycopy(left, nextIndexLeft, merged, i, left.length - nextIndexLeft); break; } if (left[nextIndexLeft] <= right[nextIndexRight]) { merged[i] = left[nextIndexLeft]; nextIndexLeft++; continue; } if (left[nextIndexLeft] > right[nextIndexRight]) { merged[i] = right[nextIndexRight]; nextIndexRight++; continue; } } System.out.println("merged : " + Arrays.toString(merged)); return merged; }просто немного отличается от исходного решения
для marge два отсортированных массива в o (m+n) временной сложности используйте ниже подход только с одним циклом. m и n-длина первого массива и второго массива.
public class MargeSortedArray { public static void main(String[] args) { int[] array = new int[]{1,3,4,7}; int[] array2 = new int[]{2,5,6,8,12,45}; int[] newarry = margeToSortedArray(array, array2); //newarray is marged array } // marge two sorted array with o(a+n) time complexity public static int[] margeToSortedArray(int[] array, int[] array2) { int newarrlen = array.length+array2.length; int[] newarr = new int[newarrlen]; int pos1=0,pos2=0; int len1=array.length, len2=array2.length; for(int i =0;i<newarrlen;i++) { if(pos1>=len1) { newarr[i]=array2[pos2]; pos2++; continue; } if(pos2>=len2) { newarr[i]=array[pos1]; pos1++; continue; } if(array[pos1]>array2[pos2]) { newarr[i]=array2[pos2]; pos2++; } else { newarr[i]=array[pos1]; pos1++; } } return newarr; } }
var arr1 = [2,10,20,30,100]; var arr2 = [2,4,5,6,7,8,9]; var j = 0; var i =0; var newArray = []; for(var x=0;x< (arr1.length + arr2.length);x++){ if(arr1[i] >= arr2[j]){ //check if element arr2 is equal and less than arr1 element newArray.push(arr2[j]); j++; }else if(arr1[i] < arr2[j]){ //check if element arr1 index value is less than arr2 element newArray.push(arr1[i]); i++; } else if(i == arr1.length || j < arr2.length){ // add remaining arr2 element newArray.push(arr2[j]); j++ }else{ // add remaining arr1 element newArray.push(arr1[i]); i++ } } console.log(newArray);
Так как вопрос не предполагает какого-либо конкретного языка. Вот решение в Python. Предполагая, что массивы уже отсортированы.
подход 1-Использование массивов numpy: импорт библиотеки numpy
arr1 = numpy.asarray([ 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 14, 15, 55]) arr2 = numpy.asarray([11, 32, 43, 45, 66, 76, 88]) array = numpy.concatenate((arr1,arr2), axis=0) array.sort()подход 2-Использование списка, предполагая, что списки отсортированы.
list_new = list1.extend(list2) list_new.sort()
вот моя реализация java, которая удаляет дубликат.
public static int[] mergesort(int[] a, int[] b) { int[] c = new int[a.length + b.length]; int i = 0, j = 0, k = 0, duplicateCount = 0; while (i < a.length || j < b.length) { if (i < a.length && j < b.length) { if (a[i] == b[j]) { c[k] = a[i]; i++;j++;duplicateCount++; } else { c[k] = a[i] < b[j] ? a[i++] : b[j++]; } } else if (i < a.length) { c[k] = a[i++]; } else if (j < a.length) { c[k] = b[j++]; } k++; } return Arrays.copyOf(c, c.length - duplicateCount); }