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

Question

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

 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]) {