一道面试题，寻求优秀的解法：对于2个一维数组，如何查找出重复的元素

Question

面试时，其中有这么一道题目：
对已有的2个一维数组，譬如说A[]，B[]，找出2个数组重复的元素。我的解答：
先对2个数组各自排序，然后再逐一比较。面试的哪位仁兄说我的答案已经比较接近，但是还有更优秀的，叫我自己再多想想。面试结束后我想了一个多小时直到现在，还是没想出如何改进。各位经过的朋友可以说说你们解决这对题目的方法吗，谢谢！

Answer 1

 我写个简单的，不知怎样，也许有更好的方法。               
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++;
}
}

Answer 2

先将一个数组进行堆排序，时间复杂度是O（NlogN）,然后枚举另一个数组的所有数字加入这个堆中，然后作维持堆结构的操作，时间复杂度是long(n)，然后删除这个数字，总是时间复杂度是O(nlogn)。

Answer 3

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));
}
        }
}

Answer 4

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]);
}
}
}
}

Answer 5

这是去年google的一道笔试大题

Answer 6

在楼主基础上稍稍再改进一点：假设 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)。

Answer 7

我想说的是，大家都知道hash算法吧，在映射的时候就会发生重复的事，那么可不可以先让一个数据映射到一个临时数组里，然后另一个数组同样映射到上面去，如果重复可能相同啊，不知道这样的效率多高，不过空间要多2个数组的长度。

Answer 8

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();
}
    }
}写了个测试代码,但是问题是 如果数组本身有重复的项,需要再过滤
觉得要看实际情况 才能写出执行效率最高的代码

Answer 9

增加一个hash表，以一个数组里的value为key填充这个hash表。
然后遍历另一个数组，对照hash表比较，就能找到重复值了。

Answer 10

13楼好强！
我只想到了第一种方法， 却没有想到用hash来作。

Answer 11

构造第一个数组的红黑树，时间复杂度为O（lgn）,并引入变量equal_amount = 0来存储相等元素的个数，然后将第二个数组的元素依次插入到构造的红黑树中，在这个过程中，若与树上某个节点的值相等，则equal_amount++;直道插入完为止，就可计算出两个数组中相等的元素个数。

Answer 12

hyzhx 
 
等 级：
 发表于：2007-11-14 22:00:1325楼 得分:0 
构造第一个数组的红黑树，时间复杂度为O（lgn）,并引入变量equal_amount   =   0来存储相等元素的个数，然后将第二个数组的元素依次插入到构造的红黑树中，在这个过程中，若与树上某个节点的值相等，则equal_amount++;直道插入完为止，就可计算出两个数组中相等的元素个数。 
 
 
Good

Answer 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]);
    }
}
}

Answer 14

我的做法也是先排序后查找。LZ当时就应该请教一下面试你的人。
还有一种做法是从集合中删除，或者取集合交集
for exampleint 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()));

Answer 15

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]);
}
}
}
}

Answer 16

其实13楼的也就是先将数组A中的元素构成一个二叉排序树，然后再到二叉树中查找数组B中的元素，找到了，就为重复的元素。
难道这就是最佳答案吗？我觉得16楼的做法跟他的是一样的，而且细节上要好点，分析得也很清楚。
13楼的做法中还有一个bug，例如：A= {1，2，3}， B={1，1，2}。那么将会返回，new ArrayList（）{1，1，2}，而不是new ArrayList{1,2}。
应该用Set来保存结果的。

Answer 17

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 + " ");
}
}
}

Answer 18

LZ 的问题 有点迷糊如果说 A数组里有重复的元素（而这个重复的元素 B 数组里没有） 也需要打印出来吗楼上几位高人只是解决了 A B重复的问题 没有解决 自身重复的问题

Answer 19

如果让写出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最后我觉得还是双循环比较时间最短,也是最优秀的方法

Answer 20

换种思路吧
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);
     }
     }
    }
    
}

Answer 21

晕倒,字符串比较难道比整数比较快?
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);
    }
  }
}

Answer 22

最近有事情，所以结贴晚了点，不过也有机会看见了更多精彩的讨论。
仔细看了所有帖子，归纳了下，并带上自己的想法，请各位指正，谢谢所有关注并热心解答的朋友。以上方法中主要分了2大类：
（1）先排序，再比较；
（2)直接比较。
很多人都想到的就是哈希进行优化，具体的各位可以参见上面的帖子。附（个人观点）：
1.13楼的受许多人推崇，但是正如41楼所说，存在漏洞，所以稍微改进下用hashSet，利用Set本身自带的不保存重复元素性质可以弥补不足，那就更完美了。通过外嵌50000次循环，2者的执行时间几乎没差别。（代码参见31楼）
2.直接采用2次循环，在同样外嵌50000次循环的情况下，执行时间远远多于采用hash后进行的查找。
3.网络凝聚力量，还有许多值得借鉴的方法，列举下：6楼提出了采用堆的结构解决 ， 19楼采用了多线程 ， 25楼采用了红黑树 ， 31楼“先排序，然后用2个指针顺序找。实际项目中我就是这么做的。” ， 38楼采用从集合中删除，或者取集合交集 ， 16楼在排序后采用了二分查找（当时我也正在考虑排序后采用二分什么的来提高，但是却忘记采用常用的hash了，真是失败。最开始考虑这道题的时候准备使用set的性能，但是却一下没想出如何查找重复元素，时间有限，结果就采用提问贴中最笨的方法了，hoho）
实际当中采用什么方法比较好，我想这与个人对知识的熟悉度与具体的条件了。
再次感谢所有的朋友。
如果路过的朋友还有什么新的点子或者方法，希望能费时贴一帖^_^

Answer 23

给出两个数组 A[]，B[]，如果楼主的意思是：找出 A和B都有的数据的话（前提A和B 自身中没有重复的数据）
我有一个思路大家可以讨论一下：1）把数组A转化成 字符串形式 a2）然后 循环 B  用B[i]在 字符串 a 里找，如果找到的话 那就是A和B都有的数据了
如果 A和B 自身都有重复的数据 那就先 把自身转换为字符串 然后做查找（出现2次以上就为重复项）