Question

编程算法题：将两个数组a、b中相同的元素提取出来，保存在数组c中，不考虑空间复杂度。

我写了算法，复杂度为O（n²），请问谁有更优异的算法？哥面试xx的时候写过一个时间复杂度比这个低的算法，他看不懂，就把我刷了，好在即使他不刷我，也不去xx，鄙视你，xx考官！哥今天让也你看看大家的智慧！xx考官的xx算法如下，欢迎大家各抒己见！
public class Main {
public void merge(int [] a,int [] b,int [] c){
int k=0;
outer: for(int i=0;i<a.length;i++){
inner: for(int j=0;j<b.length;j++){
if(a[i]==b[j]){
if(!isHave(a[i],c)){
c[k++]=a[i];break inner;
}
else{
break inner;
}
}
}
}
}
public boolean isHave(int a,int [] c){
for(int i=0;i<c.length;i++){
if(a==c[i]){
return true;
}
}
return false;
}
public static void main(String []args){
Main huawei=new Main();
int []a={1,3,5,5,7,8,5,4,3};
int []b={1,2,3,4,8,66,6,5,5,10};
int []c=new int[a.length>b.length?a.length:b.length];
huawei.merge(a,b,c);
for(int i=0;i<c.length;i++){
System.out.println(c[i]);
}
}
}

Answer 1

有nlogn的,先对两个数组进行排序,然后再拿其中的一个数字去另一个数字中二分查找.

Answer 2

额……本人不会JAVA啊

Answer 3

import java.util.Arrays;
import java.util.HashSet;
public class Test {
public static void main(String[] args) {
Integer a[]={1,3,5,5,7,8,5,4,3}, b[]={1,2,3,4,8,66,6,5,5,10};
HashSet<Integer> sa=new HashSet<Integer>(Arrays.asList(a));
sa.retainAll(Arrays.asList(b));
System.out.println(sa);
}
}
============
[1, 3, 4, 5, 8]
效率O(N)左右