题目来源,待字闺中,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”
给一个整数数组a[], 找到其中包含最多连续数的子集,比如给:15, 7, 12, 6, 14, 13, 9, 11,则返回: 5:[11, 12, 13, 14, 15] 。
分析:最简单的方法是sort然后scan一遍,但是要 o(nlgn) , 有什么 O(n) 的方法吗?网上有人用map或set来做,但map或set的复杂度还是O(nlgn)。并查集可以做到O(n),此题用并查集比较简单。
以下参考http://www.2cto.com/kf/201308/234796.html,但是该文章给的代码有缺陷,就是只能处理正数的情况
并查集是一宗简单的用途广泛的算法和数据结构。并查集是若干个不相交集合,能够实现较快的合并和判断元素所在集合的操作。应用很多,比如:求无向图的连通分量个数,实现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]。
具体见代码,该代码使用map做hash表,比原文的vector优越的地方就是可以处理负数
#include <iostream> #include <map> #include <vector> #include <assert.h> using namespace std; void Make(vector<int>& p,vector<int>& len,int x) { p[x] = x; len[x] = 1; } int Find(vector<int>& p,int x) { if(p[x] != x)p[x] = Find(p,p[x]); return p[x]; } //保证x >= y void Union(vector<int>& p,vector<int>& len,int x,int y) { int p1 = Find(p,x); int p2 = Find(p,y); if(p1 == p2)return; p[p2] = p1; len[p1] += len[p2]; } bool exist(map<int,int>& hash,int value,int x) { map<int,int>::iterator iter = hash.begin(); while(iter != hash.end()) { if(iter->first == value && iter->second == x)return true; iter ++; } return false; } bool exist(map<int,int>& hash,int value) { map<int,int>::iterator iter = hash.begin(); while(iter != hash.end()) { if(iter->first == value)return true; iter ++; } return false; } void Longest(vector<int>& ivec, int& max, int& maxLen) { assert(!ivec.empty()); int size = ivec.size(); vector<int> p(size);//并查集的父亲下标 vector<int> len(size);//该节点为根的并查集的大小 map<int,int> hash;//用于判断某一值的相邻元素是否存在 int i; for(i=0;i<size;i++)Make(p,len,i); for(i=0;i<size;i++) hash[ivec[i]] = i;//如果有重复数据,后面的数据会把前面的数据覆盖,这样可以防止重复计算 for(i=0;i<size;i++) { if(exist(hash,ivec[i],i))//加上i用于处理重复数字 { if(exist(hash,ivec[i]-1))Union(p,len,i,hash[ivec[i]-1]);//此处不需要处理重复数字是因为hash[ivec[i]-1]选中的肯定是最后一个 if(exist(hash,ivec[i]+1))Union(p,len,hash[ivec[i]+1],i);//交换位置保证Union的x > y } } max = ivec[0]; maxLen = len[0]; for(i=1;i<size;i++) { if(len[i] > len[0]) { max = ivec[i]; maxLen = len[i]; } } } int main() { int n; while(cin >> n) { vector<int> data(n); int i; for(i=0;i<n;i++)cin >> data[i]; int max,maxLen; Longest(data,max,maxLen); for(i=1;i<=maxLen;i++)cout << max - maxLen + i << " "; cout << endl; } return 0; }如有错误,请指正,谢谢
原文:http://blog.csdn.net/fangjian1204/article/details/37757967