如何取两个已排序数组的交集?

Question

例:
1,3,5,6,7,9
2,4,6,7,8,9
如何能够最快的取出交集.
有没有什么好的算法.我不想去一个一个的循环比较.

Answer 1

Apache Jakarta Commons 有 Collections 包，里面有个 CollectionUtil.intersection() 方法，就是取两个集合中的交集。但是对于你的这个问题，看样子好像需要自己设计算法。

Answer 2

一个一个的循环比较就行了，因为已经排好序了的，如果比较数>=待比较数，就break到下一轮查找，这应该已经很高效了吧……

Answer 3

因为是排好序了，可以同时搜索
int[] a = {1,3,5,6,7,9};
int[] b = {2,4,6,7,8,9};
Set s = new HashSet();
for (int i=0, j=0; i<a.length && j<b.length; ) {
    if (a[i]==b[j]) {
        s.add(""+a[i]);
        i++;
        j++;
    } else if (a[i] > b[j]){
        j++;
    } else {
        i++;
    }
}
if (s.size()==0) {
    Sytem.out.println("no intersection");
} else {
    System.out.println(Arrays.toString(s.toArrays()));
}

Answer 4

collect接口有两个方法你去看下对你很有帮助,就是取交集用的boolean retainAll(Collection<?> c)仅保留此 collection 中那些也包含在指定 collection 的元素（可选操作）。换句话说，移除此 collection 中未包含在指定 collection 中的所有元素。 
boolean removeAll(Collection<?> c)移除此 collection 中那些也包含在指定 collection 中的所有元素（可选操作）。此调用返回后，collection 中将不包含任何与指定 collection 相同的元素。 

Answer 5

如果还不了解.请看下面示例int[] a = {1,3,5,6,7,9};
int[] b = {2,4,6,7,8,9};List   list   =   new   ArrayList(Arrays.asList(a));   
list.retainAll(Arrays.asList(b));   //   list   中的就是交集了.

Answer 6

public static <T> List<T> asList(T... a)返回一个受指定数组支持的固定大小的列表。（对返回列表的更改会“直接写”到数组。）此方法同 Collection.toArray() 一起，充当了基于数组的 API 与基于 collection 的 API 之间的桥梁。返回的列表是可序列化的，并且实现了 RandomAccess。

Answer 7

用retainAll当然是最简单的代码，但是这样就体现不出排序数组的优势，
用qybao(阿宝) 的方法可减少循环次数

Answer 8

如果是未排好序的，Collection可能会快， 但是排好序的Collection就不一定见得比自己写的算法快了。如果追求代码简洁，也可以用Collection

Answer 9

在这问题上我同意bushuang的处理方式。

Answer 10

1,3,5,6,7,9
2,4,6,7,8,9用两个整型,第一位代表0,第二位1,以此类推.如果上面两组数对应整数应该是:
0101011101........
0010101111........
将这两数进行&操作不就得到交集了.
如果整数集合太大就自己做位域吧.

Answer 11

有个想法可以减少循环，因为是排好序的，所以判断如果b的一个值大于a的一个，那就不用再循环判断b后面的值是不是符合要求的，后面的值一定也大于a，例子如下：
int[] a = {1,3,5,6,7,9};
int[] b = {2,4,6,7,8,9};
ArrayList list = new ArrayList();
for(int i = 0;i < a.length;i++){
//因为是排好序的，判断当a中一个值大于b中一个值的时候就跳出不用再循环b后面的了
for(int j = 0;j < b.length;j++){
if(a[i] = j[i]){
list.add(a[i]);
}elseif(a[i] < j[i]){
return;//如果a[i]<j[i]就跳出
}else{
j++;//如果a[i]>j[i]，就j++继续循环j
}
}
i++;//然后继续循环a
}
这个虽然也循环，但是可以减少循环次数。

Answer 12

可以用set吗？要是可以拿就简单了．

Answer 13

public class t{
private int[] a={0,1,3,3,5,7,9};//去比较
private int[] b={-1,0,2,3,4,5,9,9,10};//被比较
private int[] c=null;
public t(){
c=jiaoJi(a,b); 
print(); //打印
}

public int[] jiaoJi(int[] a,int[] b){ //处理交集函数
//确定 中间变量数组 jj 的数组大小，其大小为，a,b两数组较小的数组大小
int size;
if (a.length>b.length){
size=b.length;
}else{
size=a.length;
}
                //建立中间变量数组 jj
int [] jj=new int [size]; 
for (int i=0;i<size;i++){ //赋值
jj[i]=0;
}
int k=0;//记录交集元素插入到jj数组的位置
int e=0;//记录 下一次比较的开始位置
for (int i=0;i<a.length;i++){
for (int j=e;j<b.length;j++){
if (a[i]==b[j]){
jj[k++]=a[i]; //存储交集元素，数组jj 下标 k 加一
e=j+1; //记录 下一次比较的开始位置,既从j后面的元素开始
break;//跳出for循环
}
}
}

int [] zzjj=new int[k]; //根据K建立交集的是数组zzjj
for (int i=0;i<k;i++){
zzjj[i]=jj[i];
}
return zzjj;
} public void print(){//打印
for(int i=0;i<c.length;i++){
System.out.print(c[i]+", ");
}
System.out.println();
} public static void main(String args[]){
new t();
}

}我这个也行的，测试通过

Answer 14

//C++版本
template<class  Type>
void  union_intersect(vector<Type>&  l,vector<Type>&  r,vector<Type>&  out)
{
  sort(l.begin(),l.end());
  sort(r.begin(),r.end());
  out.clear();
  vector<Type>::iterator  IL=l.begin();
  vector<Type>::iterator  IR=r.begin();
  while(IL!=l.end()&&IR!=r.end())
  {
    if(*IL<*IR)
    {
      while(IL!=l.end()&&*IL<*IR)
        ++IL;
    }
    else  if(*IR<*IL)
    {
      while(IR!=r.end()&&*IR<*IL)
        ++IR;
    }
    else
    {
      out.push_back(*IL);
      ++IL;  ++IR;
    }
  }
}

Answer 15

往hashtable里面插入啊，遇到存在的就是交集的一个数据项

Answer 16

都写的这么复杂干吗，java里提供了Set类，直接就可以算交集。

Answer 17

btw,为什么不用循环，循环是最基本的控制结构之一，有什么不好？lz怎么不说不用判断……

Answer 18

因为是排好序了，可以同时搜索
int[] a = {1,3,5,6,7,9};
int[] b = {2,4,6,7,8,9};
Set s = new HashSet();
for (int i=0, j=0; i<a.length && j<b.length; ) {
    if (a[i]==b[j]) {
        s.add(""+a[i]);
        i++;
        j++;
    } else if (a[i] > b[j]){
        j++;
    } else {
        i++;
    }
}
if (s.size()==0) {
    Sytem.out.println("no intersection");
} else {
    System.out.println(Arrays.toString(s.toArrays()));
}

Answer 19

list.retainAll 好像效率不是最高的用归并， m+n的复杂度list1 size m
list2 size n

Answer 20

//用模式匹配的算法~
public static void getPattern(Object[] strA, Object[] strB) {
// 只要有一个null，就返回null
if (strA == null || strB == null || strA.length == 0
|| strB.length == 0) {
System.out.println("");
return;
}
int lengthA = strA.length;
int lengthB = strB.length;
Object[] longStr = lengthA > lengthB ? strA : strB;
Object[] shortStr = lengthA > lengthB ? strB : strA;
Map<Integer, List<Object[]>> maxSubstrList = new TreeMap<Integer, List<Object[]>>();
for (int length = shortStr.length; length >= 0; length--) {
for (int startIndex = 0; startIndex <= shortStr.length - length; startIndex++) {
Object[] tmpO = new Object[length];
System.arraycopy(shortStr, startIndex, tmpO, 0, length);

String _tmp1 = Arrays.toString(longStr).replaceAll("\\[", "").replaceAll("\\]", "");
String _tmp2 = Arrays.toString(tmpO).replaceAll("\\[", "").replaceAll("\\]", "");
if ((_tmp1.indexOf(_tmp2) > -1) && (Arrays.asList(longStr).containsAll(Arrays.asList(tmpO)))) {
int len = tmpO.length;
List<Object[]> list;
if (maxSubstrList.containsKey(len)) {
list = (List<Object[]>) maxSubstrList.get(len);
} else {
list = new ArrayList<Object[]>();
}
if (!list.contains(tmpO)) {
list.add(tmpO);
}
maxSubstrList.put(len, list);
}
}
}
//找到所有匹配子串
if (maxSubstrList.size() == 0) {
return;
} else {
Iterator<Entry<Integer, List<Object[]>>> it = maxSubstrList
.entrySet().iterator();
Entry<Integer, List<Object[]>> entry = it.next();
while (it.hasNext()) {
entry = it.next();
List<Object[]> maxList = entry.getValue();
for (Object[] str : maxList) {
System.out.println(Arrays.toString(str));
}
}
}
}测试：getPattern(new Integer[]{1,2,4,6,7,8,9},new Integer[]{1,3,4,7,8,9,11,22});
结果：
[1]
[4]
[7]
[8]
[9]
[7, 8]
[8, 9]
[7, 8, 9]

Answer 21

遍历一个小的数组，因为有序，复杂度能够做到O(min(n,m))

Answer 22

int bIndex=0;
int num = 0;
int[] iaArray = {1,3,5,6,7,9};
int[] ibArray = {2,4,6,7,8,9};
List<Integer> newList = new ArrayList<Integer>();
A:for(Integer a : iaArray){
    B:for(int i=bIndex;i<ibArray.length;i++){
        num++;
        if(a > ibArray[i]){
          bIndex = i +1;
          continue B;
        }
        if(a = ibArray[i]){
          newList.add(a);
          continue A;
        }
        if(a < ibArray[i]){
          continue A;
        }    }
}循环11次