如何求两个数组的交集？

Question

有两个数组a{1,5,8,10,14,15,17,18,20,22,24,25,28}和b{2,4,6,8,10,12}，如何求出他们之间的交集？要求效率越高越好
注：数组都是从小到大排序好的

Answer 1

首先确定好单独的数组有无重复的，如果没有，可以先把一个数组放到set中去，比如把a放到set中去，再遍历b数组放到set中去，如果set的size没有变化，那么b中的这个元素就是重复元素，也就是所谓的交集。

Answer 2

上面这个算法 有没有排过序都可以做 但是有一点需要注意：比如我把a加到数组中，其实a中有无重复的不要紧，但是如果b中有重复的，比如有2个100，但是100恰好又不在a中，这样的情况下，上面的算法就会把100当做a和b交集的一部分，所以要避免这种情况。

Answer 3

其实解决b中的重复也很简单，只要在遍历b的时候，判断一下当前的这个元素是否和前面的元素一样，如果一样，那就continue执行下一次循环。所以总结起来看，在这个算法中，如果a是第一个放到set中去的话，那么a有没有排序无所谓；但是为了避免麻烦，b最好是排序的。好了，代码就不写了。已经分析好了。坐等楼下提供别的算法...

Answer 4

既然是排序好的,
那么可以直接对比a和b的元素
i,j是a,b中元素的当前位置
while(i<a.length && j < b.length)
{
if(a[i] < b[j])
{
    i++;
}
else if (a[i] == b[j])
{
    输出这个元素;
    i++;
    j++;
}
else
{
    j++;
}
}

Answer 5

偷懒的写法：int[] a = {1,5,8,10,14,15,17,18,20,22,24,25,28};
int[] b = {2,4,6,8,10,12};List   list   =   new   ArrayList(Arrays.asList(a));   
list.retainAll(Arrays.asList(b));   //   list   中的就是交集了.

Answer 6

import java.util.*;public class TestSet 
{
public static void main(String[] args) 
{
Set<Integer> s1 = new HashSet<Integer>();
Set<Integer> s2 = new HashSet<Integer>();
int[] a = {1,5,8,10,14,15,17,18,20,22,24,25,28};
int[] b = {2,4,6,8,10,12}; for(int i =0;i<a.length;i++) {
s1.add(a[i]);
} for(int i =0;i<b.length;i++) {
s2.add(b[i]);
} s1.retainAll(s2); //求交集
System.out.println(s1);
}
}
结果[8,10]

Answer 7

代码如下，如果你想降低时间复杂度，可以在getDuplicated方法里多加判断，因为是排过序的，当第二个数组的元素大小超过了第一个数组的最后一个值的时候，就没有必要继续了；还有当前元素如果小于第一个数组的第一个元素是，也没必要继续，直接跳到下一次循环。等等...
import java.util.*;public class STest {
private static int count, index;

public static void getDuplicated(int[] a, int[] b){
Set<Integer> set = new LinkedHashSet<Integer>();

for(int i=0; i<a.length; i++)
set.add(a[i]);

for(int j=0; j<b.length; j++){
int setSize = set.size();

if(j>0){
if(b[j] == b[j-1])
continue;
}

set.add(b[j]);

if(set.size() == setSize){
b[index] = b[j];
count ++;
index ++;
}
}
}

    public static void main(String[] args) {
     int[] first = {1,5,8,8,10,100,14,15,70,70,17,18,18,20,22,24,25,28};
     int[] second = {2,4,4,4,4,6,8,8,8,8,10,12};
    
     getDuplicated(first, second);
        
     for(int i=0; i<count; i++)
     System.out.print(second[i] +" ");
    }
}

Answer 8

如果用set的话，add重复的进去返回值是false，就不需要再判断size了

Answer 9

高效率的上面都说了，我写个低效率的，优点在于没用API中现成的方法，笔试时经常碰到这种变态要求public class TestUnion {
public static void main(String args[]){
int a[] = {1,5,8,10,14,15,17,18,20,22,24,25,28};
int b[] = {2,4,6,8,10,12};
for(int i = 0; i < b.length; i++){
for(int j = 0; j < a.length; j++){
if(b[i] == a[j]){
System.out.print(" " + b[i]);
break;
}
else
continue;
}
}
}
}

Answer 10

public class ArrayIntersection {
public static void main(String[] args) {
int[] a = { 1, 5, 8, 10, 14, 15, 17, 18, 20, 22, 24, 25, 28 };
int[] b = { 2, 4, 6, 8, 10, 12 };
int lenA = a.length;
int lenB = b.length;
for (int ai = 0, bi = 0; ai < lenA && bi < lenB;) { if (a[ai] < b[bi])
ai++;
else if (a[ai] > b[bi])
bi++;
else {
System.out.println(a[ai]);
ai++;
bi++;
}
}
}
}

Answer 11

你的算法效率是所有答案中最高的.
时间复杂度应该是O(min(a,b))吧.

Answer 12

回楼上,简单的说,for循环的次数就是min(a,b).

Answer 13

当一直是a++或b++或ab同时++的时候for循环次数是min(a,b),
当一次a++,下次b++的时候就不是了

Answer 14

int[]results=int[a.length];
int c=0;
for(int i=0;i<a.length;++i)
{
for(int j=0;j<b.length;++j)
{
if(a[i]<b[j])break;
if(a[i]==b[j])
{results[c]=a[i];++c}
}
}

Answer 15

简单明了，好代码，是不是也可用for each来遍历？

Answer 16

public void static main(String args[])
{
 int []results;
 int count=0;
 int i=j=0;
 while(i<a.length&&j<b.length)
 {
   if(a[i]==a[j])
      {
       results[c]=a[i];
       count++;
      } }
 for(int k=0;k<results.length;k++)
 System.out.print(results[k]+" ");
}

Answer 17

org.apache.commons.collections.bag.HashBag
去找这个类，直接求的交集!

Answer 18

这题很简单，5楼正解，呵呵,刚好问题是两个都是已经排好序了的数组。搞不懂怎么别人考算法的时候，很多人总喜欢调用API来弄。（1）首先用API看起来有时候代码写的很简练，其实效率低，API通用函数里面本身就有遍历或者比较等等。（2）既然是考算法，当然是考应聘人的算法和数据结构基本功底扎实否，其实API中函数别人写的时候都是用到了算法知识，有时候我们也可以运用算法封装具有自己项目特色的函数，当然做项目，有现成API可用，还是应该积极用的。

Answer 19

public static void go(int[] a, int[] b) {
int i = 0;
int j = 0; while (i < a.length && j < b.length) {
if (a[i] < b[j]) {
i++;
} else if (a[i] > b[j]) {
j++;
} else {
System.out.print(a[i] + " ");
i++;
j++;
}
}
} public static void main(String[] args) {
int[] a = { 1, 5, 8, 10, 14, 15, 17, 18, 20, 22, 24, 25, 28 };
int[] b = { 2, 4, 6, 8, 10, 12 };
go(a, b);
}
}

Answer 20

我一看就想到用Merge的思想来做  5楼正解。

Answer 21

算法的时间复杂度不是O（min(a,b)） 而是O（a+b）
很明显的 for 循环中的i,j一次只能是其中一个Counter自加（if语句）
所以 ，最好的情况是O（min（a，b）），最坏的情况是O（a+b）
好：a[]={1,3,5},b[]={9,10,12}
坏：a[]={1,12},b[]={3,5,9,10,}

Answer 22

C++ STL 函数 set_union

Answer 23

时间复杂度是o(a+b)最坏a+b,最好a或b

Answer 24

假设你的数据是字符串,可以使用二叉树,在n*Log n复杂度内能解决你的问题.
哈希表的复杂度应该是m+n=max(m,n)复杂度,线性的.

Answer 25

int k = 0;
public int[] jiao(int[] x, int[] y){ //求两个集合的交集
int[] z = new int[max(x.length, y.lengh)];

for(int i=0; i<x.length; i++){
for(int j=0; j<y.length; j++){
if(y[j] > x[i]) break;
if(y[j] == x[i]) {
z[k++] = y[j];
}
}
}
return z;
}
}

Answer 26

//#67楼code改进int k = 0;
public int[] jiao(int[] x, int[] y){ //求两个集合的交集
        int[] z = new int[max(x.length, y.lengh)];
        
        int i,j = 0;
        for(i=0; i<x.length, j<y.length; i++){
            for(j=0; j<y.length; j++){
                if(y[j] > x[i]) break;
                if(y[j] == x[i]) {
                    z[k++] = y[j];
                }
        }
        }
        return z;
    }
}

Answer 27

使用set，先把一个数组放到set中，然后循环另一个数组，将其放在set中，如果set的size没有边就说明那个数是交集中的一个元素，不过先要确保数组中没有重复的。

Answer 28

up按理说效率蛮高了
只是length可以只计算一次

Answer 29

同意46楼的说法 复杂度是O(a.length+b.length) 直到数组都遍历完了才结束循环

Answer 30

既然是排序好的, 
那么可以直接对比a和b的元素 
i,j是a,b中元素的当前位置 
Java codewhile(i <a.length&& j < b.length) 
{if(a[i] < b[j]) 
{ 
    i++; 
}elseif (a[i]== b[j]) 
{ 
    输出这个元素; 
    i++; 
    j++; 
}else 
{ 
    j++; 
} 
} 

Answer 31

设长串长度为L,短串长度为S,当L:S大于log2(L)时可以结合二分查找。

Answer 32

知道散列集HashSet 吗，它在数据组织上类似于数学上的数组，可以进行“交”、“并”、“差”等运算。
例如：
 Integer  one=new Integer(1),
          two=new Integer(2),
          three=new Integer(3),
          four=new Integer(4),
          five=new Integer(5),
          six=new Integer(6);
 HashSet A=new HashSet(),
         B=new HashSet(),
         tempSet=new HashSet();
 A.add(one); 
 A.add(two);
 A.add(three);
 A.add(four);
 B.add(one);
 B.add(two);
 B.add(five);
 B.add(six);
 tempSet=(HashSet)A.clone();
 A.removeAll(B);        //A变成调用该方法之前的A集合与B集合的差集
 B.removeAll(tempSet);  //B变成调用该方法之前的B集合与tempSet集合的差集
 B.addAll(A);           //B就是最初的A与B的交集                 

Answer 33

public List getListForPage ( final String hql , final int offset , final int length ) {              List list = getHibernateTemplate().executeFind ( new HibernateCallback ( ) {
                            public Object doInHibernate ( Session session ) throws HibernateException, SQLException {
                                            Query query = session.createQuery ( hql ) ;
                                            query.setFirstResult ( offset ) ;
                                            query.setMaxResults ( length ) ;
                                            List list = query.list ( ) ;
                                            return list ;
                           }
               }) ;
               return list ;
}