两个排序数组的交集

From Kiwi
Jump to: navigation, search

问题

找出两个排序数组的交集


代码

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int a[] = {2, 5, 6, 9, 13, 15, 16, 19, 20, 21, 23, 25, 29};
	int b[] = {1, 3, 4, 6, 9, 13, 14, 17, 19, 20, 21, 27};
	
	vector<int> v1(a, a + 13);
	vector<int> v2(b, b + 12);
	
	vector<int>::iterator iter1, iter2;
	iter1 = v1.begin();
	iter2 = v2.begin();
	
	int sameCount = 0;
	
	while( ( iter1 != v1.end() ) && ( iter2 != v2.end() ) )
	{
		if( *iter1 == *iter2 )
		{
			if( sameCount == 0 )
				cout << "--->" << endl;
			sameCount++;
			
			cout << "@: " << *iter1 << endl;
			
			iter1++;
			iter2++;
		}
		else if( *iter1 < *iter2 )
		{
			if( sameCount > 0 )
			{
				cout << "<---" << endl;
				sameCount = 0;
			}
				
			iter1++;
		}
		else
		{
			if( sameCount > 0 )
			{
				cout << "<---" << endl;
				sameCount = 0;
			}
				
			iter2++;
		}
	}
	
	if( sameCount > 0 )
	{
		cout << "<---" << *iter1 << endl;
		sameCount = 0;
	}
	
	return 0;
}


标准C++代码

void findCommonArray(int array1[], int size1, int array2[], int size2)
{
	int i = 0, j = 0;
	
	while( i < size1 && j < size2 )
	{
		if( array1[i] == array2[j] )
		{
			cout << array1[i] << ", ";
			i++;
			j++;
		}
		else if( array1[i] < array2[j] )
		{
			i++;
		}
		else
		{
			j++;
		}
	}
	
	cout << endl;
}