如何将两个有序数组合并成一个有序数组?

This was asked of me in an interview and this is the solution I provided:

这是我在一次采访中被问到的问题，这是我提供的解决方案:

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;
}

Is there a more efficient way to do this?

有没有更有效的方法?

Edit: Corrected length methods.

编辑:纠正长度的方法。

30 个解决方案

#1

A minor improvement, but after the main loop, you could use System.arraycopy to copy the tail of either input array when you get to the end of the other. That won't change the O(n) performance characteristics of your solution, though.

一个小的改进，但是在主循环之后，您可以使用系统。当你到达另一个数组的末尾时，arraycopy可以复制输入数组的尾部。不过，这不会改变解决方案的O(n)性能特征。

#2

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;
}

Is a little bit more compact but exactly the same!

有点紧凑，但完全一样!

#3

I'm surprised no one has mentioned this much more cool, efficient and compact implementation:

我很惊讶没有人提到这个更酷、更高效、更紧凑的实现:

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;
}

Points of Interests

的利益点

1. Notice that it does same or less number of operations as any other O(n) algorithm but in literally single statement in a single while loop!
2. 请注意，它与其他O(n)算法的操作数相同或更少，但在单个while循环中实际上是单个语句!
3. If two arrays are of approximately same size then constant for O(n) is same. However if arrays are really imbalanced then versions with System.arraycopy would win because internally it can do this with single x86 assembly instruction.
4. 如果两个数组的大小近似相同，则O(n)不变。然而，如果数组是真正不平衡的，那么就会有系统的版本。arraycopy将会胜出，因为它可以在内部使用单x86汇编指令。
5. Notice a[i] >= b[j] instead of a[i] > b[j]. This guarantees "stability" that is defined as when elements of a and b are equal, we want elements from a before b.
6. 注意[i] >= b[j]而不是[i] > b[j]。这保证了“稳定性”的定义，即a和b的元素相等时，我们需要a之前的元素。

#4

Any improvements that could be made would be micro-optimizations, the overall algorithm is correct.

任何可以做的改进都是微优化，总体算法是正确的。

#5

This solution also very similar to other posts except that it uses System.arrayCopy to copy the remaining array elements.

这个解决方案也非常类似于其他的帖子，只是它使用了系统。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;
}

#6

Here is updated function. It removes duplicates, hopefully someone will find this usable:

这是更新的功能。它删除了重复，希望有人会发现这个有用:

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);
}

#7

It can be done in 4 statements as below

可以在以下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)

---

#8

I had to write it in javascript, here it is:

我必须用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;
}

#9

Apache collections supports collate method since version 4; you can do this using the collate method in:

Apache collection支持自版本4以来的collate方法;你可以用collate方法来做这个:

org.apache.commons.collections4.CollectionUtils

Here quote from javadoc:

这里引用javadoc:

collate(Iterable<? extends O> a, Iterable<? extends O> b, Comparator<? super O> c)

Merges two sorted Collections, a and b, into a single, sorted List such that the ordering of the elements according to Comparator c is retained.

将两个已排序的集合a和b合并到一个单独的排序列表中，这样就保留了根据Comparator c排序元素的顺序。

Do not re-invent the wheel! Document reference: http://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/CollectionUtils.html

不要重新发明*!参考文档:http://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/CollectionUtils.html

#10

Here's a shortened form written in javascript:

这是用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;
}

#11

    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);
    }
}

#12

I think introducing the skip list for the larger sorted array can reduce the number of comparisons and can speed up the process of copying into the third array. This can be good if the array is too huge.

我认为为较大的排序数组引入跳跃表可以减少比较的次数，并且可以加快复制到第三个数组的过程。如果数组太大，这就很好了。

#13

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;
}

#14

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;
}

#15

Algorithm could be enhanced in many ways. For instance, it is reasonable to check, if a[m-1]<b[0] or b[n-1]<a[0]. In any of those cases, there is no need to do more comparisons. Algorithm could just copy source arrays in the resulting one in the right order.

算法可以在很多方面得到增强。例如，如果a[m-1] [0]或b[n-1]

More complicated enhancements may include searching for interleaving parts and run merge algorithm for them only. It could save up much time, when sizes of merged arrays differ in scores of times.

更复杂的增强可能包括搜索交错的部分和仅为它们运行合并算法。它可以节省很多时间，当合并数组的大小在几十次中存在差异时。

#16

This problem is related to the mergesort algorithm, in which two sorted sub-arrays are combined into a single sorted sub-array. The CLRS book gives an example of the algorithm and cleans up the need for checking if the end has been reached by adding a sentinel value (something that compares and "greater than any other value") to the end of each array.

这个问题与归并排序算法有关，其中两个排序子数组合并成一个有序子数组。CLRS book给出了算法的一个示例，并在每个数组的末尾添加了一个sentinel值(比较和“大于任何其他值”)，从而清除了检查结束的需要。

I wrote this in Python, but it should translate nicely to Java too:

我在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

#17

You could use 2 threads to fill the resulting array, one from front, one from back.

您可以使用两个线程来填充结果数组，一个来自前面，一个来自后面。

This can work without any synchronization in the case of numbers, e.g. if each thread inserts half of the values.

如果每个线程都插入了一半的值，那么在数字的情况下，这是可以正常工作的。

#18

GallopSearch Merge: O(log(n)*log(i)) rather than O(n)

I went ahead and implemented greybeard suggestion in the comments. Mostly because I needed a highly efficient mission critical version of this code.

我在评论中实现了greybeard的建议。主要是因为我需要一个高效的任务关键版本的代码。

• The code uses a gallopSearch which is O(log(i)) where i is the distance from the current index the relevant index exists.
• 代码使用了一个gallopSearch，它是O(log(i))，其中i是当前索引中存在的距离。
• The code uses a binarySearch for after the gallop search has identified the proper,range. Since gallop limited this to a smaller range the resulting binarySearch is also O(log(i))
• 在gallop搜索确定了合适的范围之后，代码使用了一个binarySearch。由于gallop将其限制在较小的范围内，因此产生的binarySearch也是O(log(i))
• The gallop and merge are performed backwards. This doesn't seem mission critical but it allows in place merging of arrays. If one of your arrays has enough room to store the results values, you can simply use it as the merging array and the results array. You must specify the valid range within the array in such a case.
• 奔腾和归并都是向后进行的。这看起来并不重要，但它允许数组的合并。如果其中一个数组有足够的空间存储结果值，您可以简单地将其用作合并数组和结果数组。您必须在这种情况下指定数组内的有效范围。
• It does not require memory allocation in that case (big savings in critical operations). It simply makes sure it doesn't and cannot overwrite any unprocessed values (which can only be done backwards). In fact, you use the same array for both of the inputs and the results. It will suffer no ill effects.
• 在这种情况下，它不需要内存分配(关键操作中的大节省)。它只是确保它没有，也不能覆盖任何未处理的值(只能向后执行)。实际上，对于两个输入和结果都使用相同的数组。它不会受到不良影响。
• I consistently used Integer.compare() so this could be switched out for other purposes.
• 我一直使用Integer.compare()，因此可以将它转换为其他用途。
• There's some chance I might have goofed a little and not utilized information I have previously proven. Such as binary searching into a range of two values, for which one value was already checked. There might also be a better way to state the main loop, the flipping c value wouldn't be needed if they were combined into two operations in sequence. Since you know you will do one then the other everytime. There's room for for some polish.
• 我有可能会犯一些错误，而不是利用以前证明过的信息。例如二进制搜索到两个值的范围，其中一个值已经被检查过了。可能还有一种更好的方法来声明主循环，如果将它们合并成两个操作序列，则不需要翻转c值。既然你知道你会做一个，然后另一个每次。还有一些抛光的空间。

This should be the most efficient way to do this, with time complexity of O(log(n)*log(i)) rather than O(n). And worst case time complexity of O(n). If your arrays are clumpy and have long strings of values together, this will dwarf any other way to do it, otherwise it'll just be better than them.

这应该是最有效的方法，随着时间复杂度的O(log(n)*log(i))而不是O(n)。O(n)的最坏情况时间复杂度。如果数组是块状的，并且有长串的值，这将使任何其他方法都相形见绌，否则它将会比它们更好。

It has two read values at the ends of the merging array and the write value within the results array. After finding out which is end value is less, it does a gallop search into that array. 1, 2, 4, 8, 16, 32, etc. When it finds the range where the the other array's read value is bigger. It binary searches into that range (cuts the range in half, search the correct half, repeat until single value). Then it array copies those values into the write position. Keeping in mind that the copy is, by necessity, moved such that it cannot overwrite the same values from the either reading array (which means the write array and read array can be the same). It then performs the same operation for the other array which is now known to be less than the new read value of the other array.

在合并数组的两端有两个读取值，在结果数组中有写入值。在发现哪个值更少后，它会对该数组进行快速搜索。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;
}

This should be the most efficient way to do it.

这应该是最有效的方法。

---

Some answers had a duplicate remove ability. That'll require an O(n) algorithm because you must actually compare each item. So here's a stand-alone for that, to be applied after the fact. You can't gallop through multiple entries all the way through if you need to look at all of them, though you could gallop through the duplicates, if you had a lot of them.

有些答案有重复的删除能力。这需要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;
}

---

Update: Previous answer, not horrible code but clearly inferior to the above.

更新:以前的答案，不是可怕的代码，但明显低于上面。

Another needless hyper-optimization. It not only invokes arraycopy for the end bits, but also for the beginning. Processing any introductory non-overlap in O(log(n)) by a binarySearch into the data. O(log(n) + n) is O(n) and in some cases the effect will be pretty pronounced especially things like where there is no overlap between the merging arrays at all.

另一个不必要的hyper-optimization。它不仅调用arraycopy作为结束位，而且还用于开始。通过对数据的一个binarySearch处理O(log(n))中的任何介绍性的非重叠部分。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;
}

#19

//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]);
    };
}

#20

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;
    }

#21

var arrCombo = function(arr1, arr2){
  return arr1.concat(arr2).sort(function(x, y) {
    return x - y;
  });
};

#22

My favorite programming language is JavaScript

我最喜欢的编程语言是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;
}

#23

Maybe use System.arraycopy

也许使用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;
}

#24

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 + ", ");
    }
}

Output is :

输出是:

1, 2, 3, 4, 5, 6, 8, 9, 10, 100, 999, 1001,

1、2、3、4、5、6、8、9、10、100、999、1001，

#25

You can use ternary operators for making the code a bit more compact

您可以使用三元运算符使代码更紧凑一些。

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;
}

#26

Here is my java implementation that remove duplicate.

下面是删除重复的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);
}

#27

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;
}

Just a small different from the original solution

只是和原来的溶液稍有不同。

#28

To marge two sorted array in O(m+n) time complexity use below approach with one loop only. m and n is length of first array and second array.

在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;
    }

}

#29

Since the question doesn't assume any specific language. Here is the solution in Python. Assuming the arrays are already sorted.

因为这个问题没有任何特定的语言。这是Python中的解决方案。假设数组已经排序。

Approach 1 - using numpy arrays: import numpy

方法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()

Approach 2 - Using list, assuming lists are sorted.

方法2 -使用列表，假设列表是有序的。

list_new = list1.extend(list2)
list_new.sort()

#30

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++;
            }
        }
    }
}