最多連續數的子集

給一個整數數組a[]， 找到其中包含最多連續數的子集，比如給：15, 7, 12, 6, 14, 13, 9, 11，則返回: 5:[11, 12, 13, 14, 15] 。

最簡單的方法是sort然後scan一遍，但是要 o(nlgn) ， 有什麼 O(n) 的方法嗎？

思路：

網上有人用map來做，個人覺得用map的復雜度還是O(nlgn)。並查集可以做到O(n)，但網上一直沒有看到完整的代碼，所以自己寫了一個。

先簡單介紹並查集的內容，算法導論和網上都可以找到相應的資料。

並查集是一宗簡單的用途廣泛的算法和數據結構。並查集是若干個不相交集合，能夠實現較快的合並和判斷元素所在集合的操作。應用很多，比如：求無向圖的連通分量個數，實現kruskal算法等。

並查集可以方便地進行以下三種操作：

1、Make(x)：把每一個元素初始化為一個集合，初始化後每一個元素的父節點就是它本身。

2、Find(x)：查找一個元素所在的集合，一個元素所在的集合用這個集合的祖先節點來標識。判斷兩個元素是否屬於同一個集合，只要看他們所在集合的祖先節點是否相同即可。

3、Union(x, y)：合並x、y所在的兩個集合，先利用Find()找到兩個集合的祖先，若這兩個祖先節點不是同一個節點，將其中一個祖先節點指向另一個祖先節點即可。（具體哪個祖先指向哪個祖先可以根據實際情況而定）

並查集的優化：在Find函數中，每次找祖先節點的復雜度是O(n)。當我們經過遞歸找祖先節點的時候，順便把這條路徑上的所有子孫節點都直接指向祖先，這樣下次Find的時候復雜度就變成了O(1)。

回到題目，首先調用Make(x)將每個元素變成一個並查集，然後一次掃描a[i]，查看a[i]-1是否存在，若存在調用Union(a[i], a[i]-1)；查看a[i]+1是否存在，若存在調用Union(a[i]+1, a[i])。在合並的同時更新集合的大小。接下裡的問題是怎麼判斷a[i]-1和a[i]+1是否存在，用哈希可以解決，而且復雜度是O(1)。

該題中並查集的操作都是基於下標的。我們用p[i]表示a[i]的父節點的下標，用len[i]表示以a[i]為根的集合的大小，我們合並的時候總是將較小值集合的祖先指向較大值集合的祖先，這樣就只需要記錄較大值集合的祖先節點對應的長度。最後掃描數組a[]和len[]，找到最大長度maxLen對應的a[i]。最後的結果就是：a[i]-maxLen+1, a[i]-maxLen+2, ..., a[i]。

#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

void Make(vector<int>& p, vector<int>& len, int x)
{
	p[x] = x;		//x是下標
	len[x] = 1;		//一個節點的集合長度為1
}

int Find(vector<int>& p, int x)
{
	if (x != p[x])
		p[x] = Find(p, p[x]);	//路徑壓縮，將該路徑上所有子孫節點，即集合中所有子孫節點的父節點都為根節點
	return p[x];
}

void Union(vector<int>& p, vector<int>& len, int x, int y)
{//傳參的時候，要將較大值的節點傳給x，較小值的節點傳給y
	int px = Find(p, x);
	int py = Find(p, y);
	if (px == py)
		return;
	p[py] = px;			//將py指向px
	len[px] += len[py];	//px為新的祖先，px的值要大於py的值，所以只更新px的長度即可
}

void Longest(vector<int>& ivec, int& max, int& maxLen)
{
	assert(!ivec.empty());
	int size = ivec.size();
	vector<int> p(size);
	vector<int> len(size);
	for (int i = 0; i < size; ++i)
		Make(p, len, i);
	int MAX = ivec[0];
	for (int i = 1; i < size; ++i)
	{
		if (ivec[i] > MAX)
			MAX = ivec[i];
	}
	vector<int> hash((MAX+2), -1);	//用於查找a[i]-1和a[i]+1是否存在
	for (int i = 0; i < size; ++i)
		hash[ivec[i]] = i;

	for (int i = 0; i < size; ++i)
	{
		int num = ivec[i];
		if (hash[num] == i)	//這個判斷條件用於處理重復數字，若hash[num]!=i，說明在i之後還有num重復出現，只處理最後一個即可
		{
			if (hash[num-1] != -1)
				Union(p, len, i, hash[num-1]);
			if (hash[num+1] != -1)
				Union(p, len, hash[num+1], i);
		}
	}
	max = ivec[0];
	maxLen = len[0];
	for (int i = 1; i < size; ++i)
	{
		if (len[i] > maxLen)
		{
			maxLen = len[i];
			max = ivec[i];
		}
	}
}

int main()
{
	int a[] = {15, 7, 12, 6, 14, 13, 9, 11};
	vector<int> ivec(a, a + 8);
	int max, maxLen;
	Longest(ivec, max, maxLen);
	for (int i = max-maxLen+1; i <= max; ++i)
		cout << i << ' ';
	cout << endl;
	return 0;
}