java - 如何将两个排序数组合并为一个排序数组但不使用第三个数组

Question

给定两个按升序排列的排序数组，其中一个保留额外空间以容纳两个数组的所有元素，合并两个排序数组，以便结果数组也按升序排序，而不创建第三个数组。

我几乎写了一个合并程序，但我使用了第三个数组。

Answer 1

一种方法可以如下。

1. 从较小的数组中取出第一个元素，并在较大的数组中找到它的位置（比如第 n 个位置）。

2. 现在从较小的数组中取出第二个元素，而不是从头开始，而是从第 n 个位置开始，在较大的数组中找到它的位置。

3. 现在从较小的数组中取出第三个元素并重复此过程，直到您的较小数组用完为止。

复杂性比较

1.它的最佳情况复杂度与较小数组的大小一样低。虽然最坏的情况是较小数组的大小 * 较大数组的大小。

2.如果您使用 Collection API 中的实用排序方法，即 Collection.sort() 或 Arrays.sort()，它们的复杂度在每种情况下都是O(nlogn)，其中 n= 每个数组大小的总和。因为这些方法使用归并排序。

Answer 2

public static int[] merge(int[] a, int[] b) {    
    int a_size = a.size();
    for(int i=0; i<b.size();i++ ) {
        a[a_size]= b[i];
        a_size++;
    } 
    Arrays.sort(a);
}

Answer 3

如果您没有效率问题，只需将一个数组添加到另一个数组的末尾即可。然后对这个串联的数组进行排序。

Answer 4

尝试使用 3 个指针，比如说 i、j 和 k。“i”将指向第一个数组的最后一个元素，“j”将指向第二个数组的最后一个元素，“k”将指向第一个数组的最后一个空白空间。比较 i 和 j 处的元素，取较大者将其放入 k。然后递减 k 和 i 或 j（以较大的元素为准）。继续此操作直到 i 或 j 低于 0。如果 i 在 j 之前低于 0，则从开始将第二个数组的剩余元素添加到第一个数组中。

void mergeSortedArrays(int arr1[],int arr2[],int m,int n)
{
    int i,j,k;
    i=m-1;
    j=n-1;
    k=m+n-1;
    while(i>=0&&j>=0)
    {
        if(arr1[i]>arr2[j])
        arr1[k]=arr1[i--];
        else
        arr1[k]=arr2[j--];
        k--;
    }
    while(j>=0)
    arr1[k--]=arr2[j--];
}