日期:2014-05-20  浏览次数:20810 次

一道面试题,寻求优秀的解法:对于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]);
}
}
}
}
------解决方案--------------------