【学习笔记】C++每日一记[20240612]

给定两个有序的数组，计算两者的交集

给定两个有序整型数组，数组中的元素是递增的，且各数组中没有重复元素。

第一时间解法：通过一个循环扫描array_1中的每一个元素，然后利用该元素去比较array_2中的每一个元素，如果array_1中的元素在array_2中出现，则将其加入交集。但是算法时间复杂度较高，需要二重循环来实现，其时间复杂度为 $O(n^2)$ 。没有利用“数组元素递增且没有重复元素”的条件。

常规和经典的解答：数组的二路并归法。
用变量i指向array_1的第一个元素，变量j指向array_2的第一个元素，然后执行下面的操作：
（1）如果array_1[i]等于array_2[j]，则该元素是交集元素，将其放到insection数组中，然后执行i++，j++，继续（1）、（2）、（3）的比较。
（2）如果array_1[i]大于array_2[j]，则执行j++，然后重复（1）、（2）、（3）的比较。
（3）如果array_1[1]小于array_2[j]，则执行i++，然后重复（1）、（2）、（3）的比较。
（4）一旦i等于数组array_1的长度，或者j等于数组array_2的长度，循环终止。最终数组intersection中的元素即为array_1和array_2的交集元素。


#include <iostream>
using namespace std;

int getInter(int array_1[], int len_1, int array_2[], int len_2, int intersection[])
{
	int i = 0;
	int j = 0;
	int k = 0;
	int len = 0;
	while (i < len_1 && j < len_2)
	{
		if (array_1[i] == array_2[j])
		{
			intersection[k] = array_1[i];
			i++;
			j++;
			k++;
		}
		if (array_1[i] > array_2[j])
		{
			j++;
		}
		if (array_1[i] < array_2[j])
		{
			i++;
		}
	}
	len = k;
	cout << "数据交集为：" << endl;
	for (int h = 0; h < len; h++)
	{
		cout << intersection[h] << " ";
	}
	cout << "" << endl;
	return len;
}

int main() 
{
	int array_1[5] = {2,5,6,8,9};
	int array_2[5] = {1,5,6,7,8};
	int len_1 = sizeof(array_1) / sizeof(array_1[0]);
	int len_2 = sizeof(array_2) / sizeof(array_2[0]);
	int intersection_len;
	int intersection[5];
	intersection_len = getInter(array_1, len_1, array_2, len_2, intersection);
	cout << "数据交集数量为：" << endl;
	cout << intersection_len << endl;
	cout << "done" << endl;
	return  0;
}