笔试题---求两数组相同元素
题目：现有数组A,B（两数组分别不含重复的元素），先要求输出A,B数组中相同的元素。要求时间复杂度小于O（n^2）。
解析：我们最先想到的算法是双重循环，逐个对比（部分代码见下）。
#include<iostream>using namespace std;void quicksort(int a[ ], int n){//时间关系，此处实现代码略}int main( ){int a[10] = {15,1,7,10,14,17,5,19,21,12};int b[15] = {2,4,6,8,10,14,16,18,24,22,5,7,11,12,81};quicksort(a,10);quicksotr(b,15);int i=0,j=0;while(i<10 && j<15){if(a[i]==b[j]){ cout<<a[i]<<","; ++i; ++j;}else if(a[i]<b[j]) { ++i ; }else { ++j; }}system("pause");return 0;}【方法2】
思想与方法1并无大的不同之处，只是考虑到两个数组的长度不同的情形，尤其是当一个数组很长而另一个数组很短的时候(m>>n)。对上述方法做以下改进：对短数组进行快速排序O（n*logn）,由于是短数组这点时间是很少的。顺次将长数组中的元素在短数组中查找，（此处利用二分查找）时间复杂度O（m*logn），因此，总体的时间复杂度为：O（n*logn+m*logn）< O(n*logn+m*logm) <O(n^2+m^2) 因此是满足题目要求的解法。
代码就不在此赘述了。二分查找可以参照 http://blog.csdn.net/duguyiran_z/article/details/8885875