一道面试题，寻求优秀的解法：对于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
[解决办法]
肯定是不能用排序，直接比较。
如果，可以用系统ＡＰＩ的话，用字符串处理会简单些。
[解决办法]
2楼，这样写 循环 排序没起到作用啊
[解决办法]
只要对一个数组进行排序，在比较
[解决办法]
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]);
}
}
}
}
------解决方案--------------------
这是去年google的一道笔试大题
[解决办法]
在楼主基础上稍稍再改进一点：
假设 A[].size() = LA, B[].size()= LB, LA < LB
(1)将元素较少的数组A[]排序，复杂度为 LA*log(LA)；
(2)对B[]中的每一个元素，在A[]中进行二分查找，如能找到则输出，复杂度为 LB*log(LA).
总的时间复杂度为： (LA+LB)*log(LA)
在 LA != LB 的情况下 ，稍小于楼主的 LA*log(LA) + LB*log(LB).
另外如有比较好的hash函数，可以进行hash法。首先将A[]中元素hash到各个桶中，然后对B[]中每个元素，hash到相应桶中，只和桶中的A的元素比较。hash比较均匀的话，时间复杂度可能会达到 O(LA)。
[解决办法]
我想说的是，大家都知道hash算法吧，在映射的时候就会发生重复的事，那么可不可以先让一个数据映射到一个临时数组里，然后另一个数组同样映射到上面去，如果重复可能相同啊，不知道这样的效率多高，不过空间要多2个数组的长度。
[解决办法]
package test;
public class Test {
final static int a[] = { 1, 6, 2, 8, 5, 8, 6, 9, 0 };
final static int b[] = { 4, 5, 4, 8, 7, 6, 2, 0 };
static int nowstatus = -1;
public synchronized static int getNextA() {
if (++nowstatus < a.length)
return a[nowstatus];
else
return -1;
}
public static boolean check(int temp) {
for (int i = 0; i < b.length; i++) {
if (temp == b[i])
return true;
}
return false;
}
public static void main(String[] args) {
for (int i = 0; i <= 5; i++) {
new Thread("Thread" + i) {
public void run() {
int temp;
while ((temp = getNextA()) != -1) {
if (check(temp) == true)
System.out.println(temp);
}
}
}.start();
}
}
}
写了个测试代码,但是问题是 如果数组本身有重复的项,需要再过滤
觉得要看实际情况 才能写出执行效率最高的代码
[解决办法]
牛人还真不少啊
[解决办法]
增加一个hash表，以一个数组里的value为key填充这个hash表。
然后遍历另一个数组，对照hash表比较，就能找到重复值了。
[解决办法]
13楼好强！
[解决办法]
13楼好强！
我只想到了第一种方法， 却没有想到用hash来作。
[解决办法]
两个数组合并，然后排序，不全出来了 ？
很高明
[解决办法]
构造第一个数组的红黑树，时间复杂度为O（lgn）,并引入变量equal_amount = 0来存储相等元素的个数，然后将第二个数组的元素依次插入到构造的红黑树中，在这个过程中，若与树上某个节点的值相等，则equal_amount++;直道插入完为止，就可计算出两个数组中相等的元素个数。
[解决办法]
hyzhx
等 级：
发表于：2007-11-14 22:00:1325楼 得分:0
构造第一个数组的红黑树，时间复杂度为O（lgn）,并引入变量equal_amount = 0来存储相等元素的个数，然后将第二个数组的元素依次插入到构造的红黑树中，在这个过程中，若与树上某个节点的值相等，则equal_amount++;直道插入完为止，就可计算出两个数组中相等的元素个数。
Good
[解决办法]
数据结构啊 头疼
[解决办法]
同意5楼说法！只做比较
[解决办法]
恩,这个13楼的不错
开销也不大
[解决办法]
红黑树的时间复杂度和前面用排序加二分查找是一样的，不过开阔了一下思路也好。
[解决办法]
public class Find{ public static void main(String[] args){ int[] _A = {1, 6, 2, 8, 5, 6, 9, 0}; int[] _B = {6, 2, 8, 5, 6, 9, 0}; new Find().test(_A, _B); } void test(int[] p_Source, int[] p_Target){ HashSet _Set = new HashSet(); for(int i=0; i<p_Source.length; i++){ _Set.add(new Integer(p_Source[i])); } for(int j=0; j<p_Target.length; j++){ if(!_Set.add(new Integer(p_Target[j])))System.out.println(p_Target[j]); } }}
[解决办法]
不需要排序，放到同一个容器里面，遇到冲突就打印出来。
[解决办法]
顶13楼的
向你学习
[解决办法]
jf
[解决办法]
13楼的想法比较巧 我觉得比较好
[解决办法]
不知道谁的好，呵呵！
[解决办法]
找出A组的全部唯一值，再然后出B组的全部唯一值
把两组合起来找重复值
[解决办法]
我的做法也是先排序后查找。LZ当时就应该请教一下面试你的人。
还有一种做法是从集合中删除，或者取集合交集
for example
int a[] = {1, 6, 2, 8, 5, 8, 6, 9, 0};
int b[] = {4, 5, 4, 8, 7, 6, 2, 0};
List la = Arrays.asList(a);
List lb = Arrays.asList(b);
//删除法
List result = new ArrayList(); //保存结果
for (int i=0; i<lb.size(); i++) {
if (la.remove(lb.get(i))) result.add(lb.get(i));
}
System.out.println(Arrays.toString(result.toArray()));
//交集法
la.retainAll(lb);
System.out.println(Arrays.toString(la.toArray()));
[解决办法]
public class Sort {
public static void main(String [] args) {
int a1[] = {1,6,2,8};
int a2[] = {2,4,8,8,10};
for(int i = 0; i < a1.length; i++) {
for(int j = 0; j < a2.length; j++) {
if(a1[i] == a2[j])
System.out.println(a1[i] + "=" + a2[j]);
}
}
}
}
[解决办法]
先排序，然后用2个指针顺序找。实际项目中我就是这么做的。
[解决办法]
其实13楼的也就是先将数组A中的元素构成一个二叉排序树，然后再到二叉树中查找数组B中的元素，找到了，就为重复的元素。
难道这就是最佳答案吗？我觉得16楼的做法跟他的是一样的，而且细节上要好点，分析得也很清楚。
13楼的做法中还有一个bug，例如：A= {1，2，3}， B={1，1，2}。那么将会返回，new ArrayList（）{1，1，2}，而不是new ArrayList{1,2}。
应该用Set来保存结果的。
[解决办法]
13效率很高!
[解决办法]
楼主太垃圾了！
[解决办法]
将短的数组进行快速排序
将长的数组元素在排序后的短数组里进行2分查找
不过都不知道标准答案，做了有什么用？
[解决办法]
41 楼考虑很周全，我前面也忽视了。
[解决办法]
。。。
import java.util.Arrays;import java.util.HashSet;public class FindSameElements { /** * 获取两个整型数组之间的重复元素集合 * * @param array1 * 数组参数1 * @param array2 * 数组参数2 * @return */ public static HashSet findSame(int array1[], int array2[]) { HashSet result = new HashSet();// 重复元素结果集合 HashSet set = new HashSet();// 利用HashSet来寻找重复元素 for (int i = 0; i < array1.length; i++) { set.add(array1[i]);// 把 array1 添加到 set,有过滤作用 } for (int i = 0; i < array2.length; i++) {// 遍历第二个数组 if (!set.add(array2[i])) {// 若有重复元素，add方法返回 false result.add(array2[i]);// 将重复出现的元素加入结果集合 } } return result; } public static void main(String args[]) { int a[] = { 1, 6, 2, 8, 5, 8, 6, 9, 0 }; int b[] = { 4, 5, 4, 8, 7, 6, 2, 0 }; // 获取重复元素集合 HashSet result = findSame(a, b); // 遍历输出重复元素 for (Object o : result) { System.out.print(o + " "); } }}
[解决办法]
13楼正解
[解决办法]
46楼强悍，我就喜欢用现成的高级语法！
[解决办法]
LZ 的问题 有点迷糊
如果说 A数组里有重复的元素（而这个重复的元素 B 数组里没有） 也需要打印出来吗
楼上几位高人只是解决了 A B重复的问题 没有解决 自身重复的问题
[解决办法]
防入同一个数组。排序。用冒泡判断相临的两个数。相等就输出结果；
[解决办法]
十三楼太强了，可以结贴了．
[解决办法]
如果让写出Java代码我觉得
直接双循环比较可能是最快的算法了.
难道Hashset,Hashmap内部不用比较吗?
而且还涉及对象类型转换,方法调用,这些都需要额外时间开销.
假设一次整数的比较所用时间为1,数组A,数组B
那么:
双循环比较 A.length*B.length
排序后比较 A.length*(A.length-1)/2为A的最多排序时间,B.length*(B.length-1)/2为B的最多排序时间
总时间:A.length*B.length+A.length*(A.length-1)/2+B.length*(B.length-1)/2
放入Hashmap(Hashset):
put(add)方法调用时间*A.lenght+对象包装时间*A.length+get(set)方法调用时间*A.lenght+查找(比较)是否有相同对象时间*A.length+对象解包时间*A.length+get(set)方法返回结果比较时间*A.length
最后我觉得还是双循环比较时间最短,也是最优秀的方法
[解决办法]
13楼的 张了见识
[解决办法]
换种思路吧
import java.util.*;
public class compare
{
public static void main(String[]args)
{
int a[] = {1, 6, 2, 8, 5, 8, 6, 9, 0};
int b[] = {4, 5, 4, 8, 7, 6, 2, 0};
new compare().getResult1(a, b);
}
//字符串查找,推给sun来做
public void getResult1(int[]array1 ,int[] array2){
String ar1Str ="";
String elem="";
for(int ind1=0;ind1<array1.length;ind1++){
elem= new Integer(array1[ind1]).toString();
//不相同的值加入;
if(ar1Str.indexOf(elem)==-1)
ar1Str+=elem+",";
}
for(int ind2=0;ind2<array2.length;ind2++)
{
elem = new Integer(array2[ind2]).toString();
if(ar1Str.indexOf(elem)!=-1){
System.out.println("相同元素"+elem);
}
}
}
}
[解决办法]
晕倒,字符串比较难道比整数比较快?
for(int i=0;i<A.length;i++){
for(int j=0;j<B.length;j++){
if(A[i]==B[j]){
System.out.println("发现重复元素:"+A[i]);
System.out.println("A索引:"+i+" B索引:"+j);
}
}
}