一道面试题,寻求优秀的解法:对于2个一维数组,如何查找出重复的元素
面试时,其中有这么一道题目:
对已有的2个一维数组,譬如说A[],B[],找出2个数组重复的元素。
我的解答:
先对2个数组各自排序,然后再逐一比较。
面试的哪位仁兄说我的答案已经比较接近,但是还有更优秀的,叫我自己再多想想。面试结束后我想了一个多小时直到现在,还是没想出如何改进。
各位经过的朋友可以说说你们解决这对题目的方法吗,谢谢!
------解决方案-------------------- 我写个简单的,不知怎样,也许有更好的方法。
int a[] = {1, 6, 2, 8, 5, 8, 6, 9, 0};
int b[] = {4, 5, 4, 8, 7, 6, 2, 0};
Arrays.sort(a);
Arrays.sort(b);
int i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] < b[j]) {
i++;
} else if (a[i] == b[j]) {
System.out.println(a[i]);
i++;
j++;
} else {
j++;
}
}
------解决方案--------------------两个数组合并,然后排序,不全出来了 ?
------解决方案--------------------2楼的比较牛啊=/=
------解决方案--------------------我感觉这个题的关键在于“优秀”,就是说计算机做什么运算是最快的。
这个题有两个要点,一个是大家都说的“排序”,这个算法要内存空间和不同算法存取的开销;而另一种大家没有明确提到,我认为是“比较”,比较是比排序开销小的多的,所以我想最好的算法反而是不排序,只比较,要比较m*n次即可。而排序时已经有了比较,而又有别的开销。
我的算法非常简单,说下就行了,不排序,只比较,双循环搞定。
------解决方案--------------------先将一个数组进行堆排序,时间复杂度是O(NlogN),然后枚举另一个数组的所有数字加入这个堆中,然后作维持堆结构的操作,时间复杂度是long(n),然后删除这个数字,总是时间复杂度是O(nlogn)。
------解决方案--------------------前几天去腾讯面试也出这个题了~
------解决方案--------------------直接循环比较不就可以了吗,不用排序的吧
------解决方案--------------------6楼牛B
------解决方案--------------------肯定是不能用排序,直接比较。
如果,可以用系统API的话,用字符串处理会简单些。
------解决方案--------------------2楼,这样写 循环 排序没起到作用啊
------解决方案--------------------只要对一个数组进行排序,在比较
------解决方案--------------------Java code
public class Test{
/**
* 获取两个整型数组之间的重复元素集合
* @param array1 数组参数1
* @param array2 数组参数2
* @return
*/
public List findSame(int array1[],int array2[]){
List result=new ArrayList();//重复元素结果集合
HashMap hashMap=new HashMap();//利用hashmap来寻找重复元素
for(int i=0;i<array1.length;i++){//将第一个数组加入hashmap
String temp=array1[i]+"";
hashMap.put(temp,temp);
}
for(int i=0;i<array2.length;i++){//遍历第二个数组
String temp=array2[i]+"";
if(hashMap.get(temp)!=null){//在已经存在第一个数组所有元素的hashmap里寻找第二数组里的元素
result.add(array2[i]);//将重复出现的元素加入结果集合
}
}
return result;
}
public static void main(String args[]){
long timeBegin=System.currentTimeMillis();
int a[] = {1, 6, 2, 8, 5, 8, 6, 9, 0};
int b[] = {4, 5, 4, 8, 7, 6, 2, 0};
//获取重复元素集合
List list=new Test().findSame(a, b);
//遍历输出重复元素
for(int i=0;i<list.size();i++){
System.out.println(list.get(i));
}
}
}
------解决方案--------------------
int i = 0, j = 0; int c=0;
if (a.length<b.length)
{
c=b.length-a.length;
for(i=0;i<a.length;i++)
{
for(j=0;j<a.length+c;j++)
{
if(a[i]==b[j])
{
System.out.println(a[i]);
}
}
}
}
------解决方案--------------------