如何将两个有序数组合并到一个有序数组中？
这是在面试中问我的，这是我提供的解决scheme：
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; } 有没有更有效的方法来做到这一点？
编辑：更正长度的方法。
一个小的改进，但在主循环之后，当你到达另一个input数组的末尾时，你可以使用System.arraycopy复制这个input数组的尾部。 尽pipe如此，这不会改变您的解决scheme的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--]; }
兴趣点
- 请注意，它与其他O（n）algorithm的操作数相同或更less，但是在单个while循环中按字面单个语句进行操作！
- 如果两个数组大小大致相同，那么对于O（n）的常数是相同的。 但是，如果数组真的不平衡，那么带有
System.arraycopy版本将会赢，因为在内部它可以用单个x86汇编指令来完成。 - 注意
a[i] >= b[j]而不是a[i] > b[j]。 这保证了当a和b的元素相等时定义的“稳定性”，我们需要a之前的元素。
任何可以进行的改进都是微观优化，整个algorithm是正确的。
这个解决scheme也非常类似于其他职位，除了它使用System.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; }
这里是更新的function。 它删除重复，希望有人会发现这个可用：
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; }
这是用javascript编写的缩写forms：
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;
}
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); } }
我认为为更大的sorting数组引入跳过列表可以减less比较次数，并且可以加速复制到第三个数组的过程。 如果数组太大，这可能会很好。
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; }
从4版开始Apache集合支持整理方法; 你可以使用下面的collate方法来做到这一点：
org.apache.commons.collections4.CollectionUtils
这里引用javadoc：
collate(Iterable<? extends O> a, Iterable<? extends O> b, Comparator<? super O> c)将两个已sorting的集合
a和b合并到一个已sorting的List中，以便保留根据比较器c的元素sorting。
不要重新发明轮子！ 文档参考： http : //commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/CollectionUtils.html
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; }
此问题与mergesortalgorithm相关，其中两个已sorting的子数组合并成一个已sorting的子数组。 CLRS书籍给出了一个algorithm的例子，并通过在每个数组的末尾添加一个标记值（比较结果“比任何其他值更大”）来清除是否已经达到结束的需求。
我用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
//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; }
algorithm可以在许多方面得到增强。 例如，检查a[m-1]<b[0]或b[n-1]<a[0]是否合理。 在任何一种情况下，都不需要进行更多的比较。 algorithm可以按照正确的顺序复制源数组。
更复杂的增强可能包括search交错部分和运行合并algorithm只。 它可以节省很多时间，当合并数组的大小不同的时候。
也许使用System.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 class Program { public static void Main(string[] args) { int[] arr = new int[] { 5, 3, 8, 7, 6, 9, 2, 11 }; int[] SortedArr = sortArr(arr); for (int i = 0; i < SortedArr.Length; i++) { Console.WriteLine(SortedArr[i]+""); } } static int[] sortArr(int[] arr) { if (arr.Length == 1) return arr; else if (arr.Length == 2) { int[] sArr = new int[2]; if (arr[0] < arr[1]) return arr; else return new int[] { arr[1], arr[0] }; } int[] retArr = new int[arr.Length]; int mIndex = arr.Length / 2; int[] leftArr = new int[mIndex]; int[] RightArr = new int[arr.Length - mIndex]; for (int i = 0; i < mIndex; i++) leftArr[i] = arr[i]; for (int i = mIndex; i < arr.Length; i++) RightArr[i - mIndex] = arr[i]; int[] sLeftArr = sortArr(leftArr); int[] sRightArr = sortArr(RightArr); int lIndex = 0, rIndex = 0; for (int i = 0; i < retArr.Length; i++) { if (lIndex == sLeftArr.Length) retArr[i] = sRightArr[rIndex++]; else if (rIndex == sRightArr.Length) retArr[i] = sLeftArr[lIndex++]; else if (sLeftArr[lIndex] < sRightArr[rIndex]) retArr[i] = sLeftArr[lIndex++]; else retArr[i] = sRightArr[rIndex++]; } return retArr; } }
您可以使用三元运算符来使代码更加紧凑
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; }
这是我的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); }
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; }
只是与原来的解决scheme有一点不同
由于这个问题没有任何特定的语言。 这是Python中的解决scheme。 假设数组已经sorting。
方法1 – 使用numpy数组：import 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 – 使用列表，假设列表sorting。
list_new = list1.extend(list2) list_new.sort()
import java.util.Arrays; public class MergeTwoArrays { static int[] arr1=new int[]{1,3,4,5,7,7,9,11,13,15,17,19}; static int[] arr2=new int[]{2,4,6,8,10,12,14,14,16,18,20,22}; public static void main(String[] args){ int FirstArrayLocation =0 ; int SecondArrayLocation=0; int[] mergeArr=new int[arr1.length + arr2.length]; for ( int i=0; i<= arr1.length + arr2.length; i++){ if (( FirstArrayLocation < arr1.length ) && (SecondArrayLocation < arr2.length)){ if ( arr1[FirstArrayLocation] <= arr2[SecondArrayLocation]){ mergeArr[i]=arr1[FirstArrayLocation]; FirstArrayLocation++; }else{ mergeArr[i]=arr2[SecondArrayLocation]; SecondArrayLocation++; } } else if(SecondArrayLocation < arr2.length){ mergeArr[i]=arr2[SecondArrayLocation]; SecondArrayLocation++; }else if ( FirstArrayLocation < arr1.length ){ mergeArr[i]=arr1[FirstArrayLocation]; FirstArrayLocation++; } } } }
