java - 合并两个数组而不使用额外空间

Question

我有 2 个排序数组，a1 和 a2，长度分别为 l1 和 l2。数组 a2 在长度为 l1 的末尾有空白空间，因此除了它自己的元素外，它还可以容纳 a1 的所有元素.现在，我想将 a1 合并到 a2 中，这样 a2 将包含 a1 和 的所有元素>a2 按排序顺序排列。理想情况下，这应该使用 O(1) 辅助存储空间。我有以下 cod,e 但出了点问题:

 public static int[] merge(int []a1,int a2[],int l1, int l2){

         System.out.println("l1 =" +l1 + " l2=" +l2);
         int es = l2-l1;
         int fs = l2-es;

         System.out.println("es= " +es);
         System.out.println("fs = " + fs);
         int j=0;

         for(int i=0;i< l1;i++){

             if(j<fs){
                // System.out.println("i= " + i + "a1[i]=" + a1[i]);
                // System.out.println("j= " + j + "a2[j]=" + a2[j]);
                 if(a1[i]<a2[j]){
                     add(a2,j,a1[i],l2);
                     //i++;
                     fs++;
                 }
             }else{
                 System.out.println("***");
                 a2[j]=a1[i];
             }

             j++;
         }

         return a2;
     }


    public static void add(int []a,int p,int key,int l){

        for(int i=l-1;i>p;i--){
              a[i]= a[i-1];
        }
        a[p]= key;
    }

有人知道如何解决这个问题吗？我使用以下数据来运行代码:

int a1[]= new int[]{-1,0,7,8};
int a2[]= new int[7];
a2[0]=1;
a2[1]=3;
a2[2]=9;

输出是

l1 =4 l2=7
es= 3
fs = 4
-1
0
1
3
9
0
0

Answer 1

很难说出您的代码做了什么，但它似乎具有次优的 (O(n^2)) 复杂度:add 方法中有第二个循环。
另外，请注意 fs 始终等于 l1。

但是还有更简单的方法:从后面。想想看，空间总是够用的。

像这样

int i = l1 - 1;
int j = l2 - 1;
int result_pos = l1 + l2 - 1;
while (i >= 0 || j >= 0) {
    if (a1[i] >= a2[j]) {
        a2[result_pos--] = a1[i--];
    } else {
        a2[result_pos--] = a2[j--];
    }
}

PS 您需要为循环中 i 和 j 之一为负的情况添加处理。显然，在这种情况下，应该复制另一个元素。

编辑
以后可以用这个条件来完成

if (j < 0 || (i >= 0 && a1[i] >= a2[j])) {

代替

if (a1[i] >= a2[j]) {