leetcode349. 兩個陣列的交集

給定兩個陣列，撰寫一個函式來計算它們的交集，

示例：
?輸入：nums1 = [1, 2, 2, 1], nums2 = [2, 2]
?輸出：[2]

思路：
按照我們做數學題時求交集的方法就行了，但注意在求交集前先分別對兩個陣列的元素進行去重，

求兩個陣列的交集的步驟可分為以下三步：

1. 對nums1當中的元素進行去重，得到序列s1，
2. 對nums2當中的元素進行去重，得到序列s2，
3. 遍歷s1，依次判斷s1中的每個元素是否在s2當中出現，若沒有出現則為交集元素，

代碼如下：

class Solution {
public:
	vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
		//1、對nums1當中的元素進行去重，得到序列s1
		set<int> s1;
		for (auto e : nums1)
		{
			s1.insert(e);
		}
		//2、對nums2當中的元素進行去重，得到序列s2
		set<int> s2;
		for (auto e : nums2)
		{
			s2.insert(e);
		}
		//3、遍歷s1，依次判斷s1中的每個元素是否在s2當中出現，若沒有出現則為交集元素
		vector<int> vRet;
		for (auto e : s1)
		{
			if (s2.find(e) != s2.end())
			{
				vRet.push_back(e);
			}
		}
		return vRet;
	}
};

時間復雜度： O ( N l o g N ) O(NlogN) O(NlogN)

優化思路：
上述代碼中，先使用set容器對兩個陣列進行去重，然后在s2序列中分別查找s1序列的元素是否存在，set容器的底層是用紅黑樹實作的，在set容器當中查找元素時的時間復雜度是 O ( l o g N ) O(logN) O(logN)，因此上述代碼整體的時間復雜度是 O ( N l o g N ) O(NlogN) O(NlogN)，

由于set容器去重后的序列是有序的，因此在這里我們可以利用雙指標的思想將時間復雜度優化到 O ( N ) O(N) O(N)，在用set容器對兩個陣列的元素進行去重后，使用雙指標從去重后兩個序列的第一個元素開始比較：

1. 若兩個指標指向的元素不相等，則小的一個元素屬于差集，小的指標往后走，
2. 若兩個指標指向的元素相等，則該元素屬于交集，兩個指標同時往后走，
3. 若其中一個序列走完了，則另一個序列剩下的元素都屬于差集，

使用雙指標進行處理，在 O ( N ) O(N) O(N)的時間復雜度下既能求出交集，還能同時求出差集，

動圖演示：

拓展：該演算法常用于同步資料，求出服務器和客戶端之間資料的差集，進而將服務器上多的資料下載到客戶端，將客戶端上多的資料上傳到服務器，最終做到資料同步，

優化代碼如下：

class Solution {
public:
	vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
		//1、對nums1當中的元素進行去重，得到序列s1
		set<int> s1;
		for (auto e : nums1)
		{
			s1.insert(e);
		}
		//2、對nums2當中的元素進行去重，得到序列s2
		set<int> s2;
		for (auto e : nums2)
		{
			s2.insert(e);
		}
		//3、使用雙指標找出s1和s2的交集
		vector<int> vRet;
		set<int>::iterator it1 = s1.begin();
		set<int>::iterator it2 = s2.begin();
		while (it1 != s1.end() && it2 != s2.end())
		{
			if (*it1 < *it2) //兩個指標指向的元素不相等
			{
				it1++; //小的往后走
			}
			else if (*it2 < *it1) //兩個指標指向的元素不相等
			{
				it2++; //小的往后走
			}
			else //兩個指標指向的元素相等
			{
				vRet.push_back(*it1); //該元素屬于交集
				//兩個指標一起往后走
				it1++;
				it2++;
			}
		}
		return vRet;
	}
};

時間復雜度： O ( N ) O(N) O(N)