Question

java中，两个已排序数组求并集的题，要求时间复杂度O(m+n)

如题

Answer 1

public class Exam
{
public static void main(String[] args)
{
int[] a={1,5,5,20,88,88,88,125,500,1001};
int[] b={2,2,5,14,16,20,87,88,88,100,129,500};

for(int n : combination(a,b))
System.out.printf("%d ",n);
}
static int[] combination(int[] a,int[] b)
{
int lena=a.length,lenb=b.length;
int lenc=lena+lenb;
int[] c=new int[lenc];
int i=0,j=0,k=0;

while(i<lena&&j<lenb)
{
if(a[i]<b[j])
c[k++]=a[i++];
else
c[k++]=b[j++];
}
for(;i<lena;i++)
c[k++]=a[i];
for(;j<lenb;j++)
c[k++]=b[j];
// System.out.println("a.length="+i);
// System.out.println("b.length="+j);
// System.out.println("c.length="+k);
return c;
}
}