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

Question

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

Answer 1

那就放到数据库里 去取 ，一个select搞定

Answer 2

如果你保证每个已排序数组中都没有重复的，
那么将数组a中数据全部插入数组b，从b里边找有重复的项就可以这算法写起来可能比较简单，但实际上时间复杂度可能还不如循环比较-_-

Answer 3

int[] a = new int[m];
int[] b = new int[n];
ArrayList andData = new ArrayList();
//a与b的初始化
int j = 0;
for(int i = 0;i < m;i++)
{
   do
   {
      if(a[i] == b[j])
      {
         andData.Add(a[i]);
         break;
      }
      j++;
   }while(j < n && a[i] != b[j])
}
return andData;

Answer 4

1. add 1,3,5,6,7,9 to hash table, key and value use the same value.
2.foreach(int key in 2,4,6,7,8,9) {
if(hashtbl[key]!=null)
{
   hashtbl[key] ----is the data you want.
}
}

Answer 5

放两个List里,表面效率为O(n); List<int> lst1 = new List<int>() { 1, 3, 5, 6, 7, 9 };
 List<int> lst2 = new List<int>() { 2, 4, 6, 7, 8, 9 };
 for (int i = 0; i < lst1.Count; i++)
 {
    if (lst2.Contains(lst1[i]))
    {
      Console.WriteLine(lst1[i]);
    }
}

Answer 6

2008 非常简单
 
            int[] A=new []{1,2,3,4,5};
            int[] B=new []{2,4,9,10};            int[] C=A.Intersect(B).ToArray();  

Answer 7

2008下用linq相当简单，而且效率很高，参考15楼代码

Answer 8

没环境 大概就是这个意思
int[] A=new []{1,2,3,4,5};
int[] B=new []{2,4,9,10};
int i,j;
i=0;
j=0;
while(true)
{
    if(i>=A.Length)
break;
    if(j>=B.Length)
break;
    if(A[i]>B[j])
j++;         
    if((A[i]<B[j])
        i++;
    if((A[i]=B[j])
    {
        Console.WriteLine(A[i]);
        i++;
        j++;
    }
}

Answer 9

刚才有问题
int[] A=new []{1,3,5,6,7,9 }; 
int[] B=new []{2,4,6,7,8,9};
int i,j;
i=0;
j=0;
while(true)
{
    if(i>=A.Length)
break;
    if(j>=B.Length)
break;
    if((A[i]=B[j])
    {
        Console.WriteLine(A[i]);
        i++;
        j++;
    }
    if(A[i]>B[j])
j++;         
    if((A[i]<B[j])
        i++;
}

Answer 10

20楼这个算法是真正的O(N)复杂度。
改正一些错误和重新格式了一下：    int[] A = { 1, 3, 5, 6, 7, 9 };
    int[] B = { 2, 4, 6, 7, 8, 9 };    int i = 0, j = 0;
    while ( i<A.Length && j < B.Length )
    {
        if (A[i] == B[j])
        {
            Console.WriteLine(A[i]);
            i++;
            j++;
        }
        else if (A[i] > B[j]) j++;
        else if (A[i] < B[j]) i++;
    }
 6楼 O(N*LogM)
 7楼 O(N*M)
11楼 O(M)，可能退化，空间复杂度高
12楼 O(N*M)
15楼 O(M)，内部用哈什，同样可能退化，空间复杂度高hash table的优势在于不要求数据事先排序，在数据已经排序的情况下，它（算法上）不是最优。
另外一点，hash table方式适用于集合（集合元素不重复），比如对下面的排序数据，15楼返回{2,9}，20楼返回{2,2,9}:
int[] A= {2,2,3,4,9};
int[] B= {2,2,9,10};