合并两个数组而不使用额外的空间 [英] Merging two arrays without using extra space

问题描述

我有2个排序数组， a1 和 a2 ，长度 l1 和 l2 。数组 a2 在长度 l1 的末尾有空格，因此它可以容纳<$的所有元素c $ c> a1 除了自己的元素。现在，我想将 a1 合并到 a2 中，以便 a2 将按排序顺序包含 a1 和 a2 的所有元素。理想情况下，这应该使用O（1）辅助存储空间。我有以下鳕鱼，但是出了点问题：

I have 2 sorted arrays, a1 and a2, of lengths l1 and l2, respectively. The array a2 has empty space at the end of length l1, so it can hold all of the elements of a1 in addition to its own elements. Now, I want to merge a1 into a2 so that a2 will contain all the elements of a1 and a2 in sorted order. Ideally this should use O(1) auxiliary storage space. I have the following cod,e but something is going wrong:

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

有没有人对如何解决这个问题有任何想法？我使用以下数据来运行代码：

Does anyone have any ideas on how to fix this? I used following data to run the code:

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

推荐答案

很难说你的代码做了什么，但似乎有一个次优（ O（n ^ 2））的复杂性：里面有第二个循环方法。

另外，请注意 fs 总是等于 l1 。

It's difficult to tell what your code does, but it seems to have suboptimal (O(n^2)) complexity: there's a second loop inside add method.
Also, note that fs is always equal to l1.

但是有更简单的方法：从后面开始。如果你考虑一下，总有足够的空间。

But there's much simpler method: from the back. If you think about it, there's always enough space.

这样的东西

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 中的一个在循环中为负数时。显然，在这种情况下，应该复制另一个元素。

PS You'll need to add handling for the case when one of i and j is negative in the loop. Obviously, in this case another element should be copied.

编辑


以后可以用这个条件完成

edit
Later can be done with this condition

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

而不是

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

这篇关于合并两个数组而不使用额外的空间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！