做网站的公司销售话术,模具外发加工订单网,微信开发小程序需要多少钱,重庆专业的网站建设公司哪家好并查集的定义
将n个不同的元素划分成一些不相交的集合。开始时#xff0c;每个元素自成一个单元素集合#xff0c;然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(unio…并查集的定义
将n个不同的元素划分成一些不相交的集合。开始时每个元素自成一个单元素集合然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union find set)
并查集的抽象描述 struct UnionFindSet 属性 数个不相交的集合,通过数组管理 vector 方法 检查两个元素是否属于同一个集合 bool inSameSet(e1,e2); 寻找集合的根元素 e findEigen(e) ; 合并两个元素所在的集合 void merge(e1,e1); 计算当前集合个数 size_t getCnt(); 如何表示同一个集合的元素 可以借助数组抽象结构的方法对同一集合的元素进行分类为了方便后续把代表某个集合的元素成为特征元素 首先把每一个元素都被映射成了一个唯一的编号idid同时也作为数组的下标 规定每一个下标所对应值为集合中其他元素的编号id如果数组中某一个id位置的值为-x代表它是一个特征元素,并且集合中有x个元素
:ufs(n,-1){} //初始状态所有的元素都各自为一个集合元素之间没有任何关系unsigned int getCnt(){unsigned int cnt0;for(int x:ufs) if(x-1) cnt;return cnt;} //统计ufs数组中-1的个数即可获得集合个数unsigned int findEigen(unsigned int e){ unsigned int eigenvale;while(ufs[eigenval]0) eigenvalufs[eigenval];return eigenval;} //迭代向上寻找直至数组中的值为-1bool inSameSet(unsigned int e1,unsigned int e2){return findEigen(e1)findEigen(e2);}void merge(unsigned int e1,unsigned int e2){unsigned int eigen1findEigen(e1);unsigned int eigen2findEigen(e2);if(eigen1!eigen2) {ufs[eigen1]ufs[eigen2];ufs[eigen2]eigen1;}//把e2所在集合的特征元素对应的值改为e1所在集合的特征元素即可完成2个集合的合并}
};优化合并与查找
合并优化小集合合并到大集合中做到更多的元素能在短时间内找到特征元素
void merge(unsigned int e1,unsigned int e2)
{unsigned int eigen1findEigen(e1);unsigned int eigen2findEigen(e2);if(eigen1!eigen2){if(ufs[eigen1]ufs[eigen2]) swap(eigen1,eigen2); //统一规定集合eigen1的元素个数更大ufs[eigen1] ufs[eigen2];ufs[eigen2]eigen1;}
}查找优化最理想的情况是每一个节点至多一次找到所在集合的特征元素 可以考虑每一次进行findEigen查找时对集合元素关系进行调整使得每一个元素在集合中更接近特征元素
unsigned int findEigen(unsigned int e)
{unsigned int eigen e, prev -1;while (_ufs[eigen] 0) {int tmp ufs[eigen];//向上查找if (prev0) ufs[prev] tmp;prev eigen;eigen tmp;}return eigen;
}上述代码未经测试可能存在bug经测试版代码请参考https://gitee.com/chxchenhaixiao/test_c/blob/master/UnionFindSet/UnionFindSet.h LRU cache
LRU是Least Recently Used的缩写意思是最近最少使用它是一种Cache替换算法 简单地说就是淘汰长久未使用的数据cache的大小是固定有限的当空间满时如果还需要加入数据就必须淘汰部分先前的数据
可以把每一个数据块通过一个双向链表级联人为规定链表尾节点为长时间未使用即将被淘汰的资源链表头节点为最近使用的数据借助哈希表实现对各个数据块的快速定位达到增删查改的时间复杂度均为O1 代码实现
class LRUCache {size_t _size0; //链表当前长度size_t _capacity; //cache最大容量listpairint,int _list;typedef listpairint,int::iterator iterator;unordered_mapint,iterator _map;
public:LRUCache(int capacity) :_capacity(capacity){}int get(int key) {if(!_map.count(key)) return -1;iterator it_map[key];int valit-second;_list.push_front(*it);_list.erase(it);_map[key]_list.begin();return val;}void put(int key, int value) {if(_map.count(key)) //更新节点{iterator it_map[key];it-secondvalue;_list.push_front(*it);_list.erase(it);_map[key]_list.begin();}else{if(_size_capacity){_size;_list.push_front({key,value});_map[key]_list.begin();}else{auto last_list.back(); //获取链表尾节点_map.erase(last.first); //删除map中指向尾的映射关系_list.pop_back(); //删除链表尾节点_list.push_front({key,value}); //头插_map[key]_list.begin(); //更新map}}}
};
