腾讯实习笔试：关于几个有序数组求交集的问题_多个有序数字怎么找交集

题目就是假设有三个有序数组对其求交集，要求算法空间复杂度必须小，有序数组量会比较大。
解法：
第一种就是用二分法查找，二分法查找的效率是log(n),两个数组求交集就是n1log(n2),当n1远小于n2的时候，这个算法效果可以
第二种就是遍历，用两个游标来实现，具体可以见代码，算法效率o(n1+n2)线性，当n1和n2比较接近时效果可以

#include<iostream>
#include<cstdlib>
#include<vector>
#include<list>
#include<algorithm>
#include<ctime>

using std::vector;
using std::list;

//获取一个大小为num,有序的数组vecInt,数组中最大的数值为 max*num
void getRandOrderIntVec(vector<int>& vecInt, int num,int max)
{
   
	vecInt.clear();
	vecInt.reserve(num);
	while (vecInt.size() < num)
	{
   
		if (vecInt.empty())
		{
   
			int value = (std::rand() % (max));
			vecInt.push_back(value);
		}
		else 
		{
   
			int value = (std::rand() % max ) + vecInt.back() + 1;
			vecInt.push_back(value);
		}
	}

}

//********************遍历法查找相同的数据**********************************
//找出三个数组中相同的数值，并且保存在vecSame的vector中
void getSameValue(vector<int>& vec1, vector<int>& vec2, vector<int>& vec3, vector<int>& vecSame)
{
   
	vecSame.clear();

	//先确定一个保存交集的空间大小
	int minNumInThreeVec = vec1.size();
	if (vec2.size() < minNumInThreeVec)
	{
   
		minNumInThreeVec = vec2.size();
	}
	if (vec3.size() < minNumInThreeVec)
	{
   
		minNumInThreeVec = vec3.size();
	}
	minNumInThreeVec /= 2; 

	vecSame.reserve(minNumInThreeVec);

	//***********************查找交集**************************
	vector<int>::iterator vecIter1 = vec1.begin();
	vector<int>::iterator vecIter2 = vec2.begin();
	vector<int>::iterator vecIter3 = vec3.begin();

	while ((vecIter1 != vec1.end())
		& (vecIter2 != vec2.end())
		& (vecIter3 != vec3.end())
		)
	{
   
		//如果相等的话
		if (
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70