MyException - 我的异常网
当前位置:我的异常网» J2SE » 一道面试题,寻求优秀的解法:对于2个一维数组,怎

一道面试题,寻求优秀的解法:对于2个一维数组,怎么查找出重复的元素

www.MyException.Cn  网友分享于:2013-03-05  浏览:59次
一道面试题,寻求优秀的解法:对于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]);
}
}
}
}
------解决方案--------------------

文章评论

鲜为人知的编程真相
鲜为人知的编程真相
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
漫画:程序员的工作
漫画:程序员的工作
代码女神横空出世
代码女神横空出世
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
10个调试和排错的小建议
10个调试和排错的小建议
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
程序员的鄙视链
程序员的鄙视链
程序员应该关注的一些事儿
程序员应该关注的一些事儿
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
总结2014中国互联网十大段子
总结2014中国互联网十大段子
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员必看的十大电影
程序员必看的十大电影
如何成为一名黑客
如何成为一名黑客
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
每天工作4小时的程序员
每天工作4小时的程序员
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
一个程序员的时间管理
一个程序员的时间管理
我是如何打败拖延症的
我是如何打败拖延症的
中美印日四国程序员比较
中美印日四国程序员比较
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
旅行,写作,编程
旅行,写作,编程
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
为什么程序员都是夜猫子
为什么程序员都是夜猫子
那些争议最大的编程观点
那些争议最大的编程观点
程序员都该阅读的书
程序员都该阅读的书
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
老程序员的下场
老程序员的下场
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
Java程序员必看电影
Java程序员必看电影
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有