地情网站建设方案,wordpress 数据表前缀,网站搜索建设,做一个网络公司需要多少钱目录
并查集定义
LeetCode128.最长连续序列
先去重再sort#xff1a;
改进去重的方法#xff1a;
参考#xff1a; 并查集定义
在计算机科学中#xff0c;并查集是一种树型的数据结构#xff0c;用于处理一些不交集#xff08;Disjoint Sets#xff09;的合并及查…目录
并查集定义
LeetCode128.最长连续序列
先去重再sort
改进去重的方法
参考 并查集定义
在计算机科学中并查集是一种树型的数据结构用于处理一些不交集Disjoint Sets的合并及查询问题。有一个联合-查找算法Union-find Algorithm定义了两个用于此数据结构的操作 Find确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。 Union将两个子集合并成同一个集合。 由于支持这两种操作一个不相交集也常被称为联合-查找数据结构Union-find Data Structure或合并-查找集合Merge-find Set。
为了更加精确的定义这些方法需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素称为代表以表示整个集合。接着Find(x)Find(x)Find(x) 返回 xxx 所属集合的代表而 Union 使用两个集合的代表作为参数。
LeetCode128.最长连续序列 先去重再sort
不满足O(N)复杂度的要求但是却可以击败99%离谱…… class Solution {
public:int longestConsecutive(vectorint nums) {if (nums.empty())return 0;int ans 1, len 0;// 去重unordered_setint s(nums.begin(), nums.end());vectorint v(s.begin(), s.end());sort(v.begin(), v.end());for (int i 1; i v.size(); i) {if (v[i] v[i - 1] 1) {len;} else {if (len 0) {continue;} else {ans max(ans, len 1);len 0;}}}// 进行到最后一个字符的时会出现统计疏漏需要特别判断一下if (len ! 0) {ans max(ans, len 1);len 0;}return ans;}
};
改进去重的方法
很快提高了空间复杂度理论上时间复杂度是有提高的但是LeetCode大数测试点肯定是有问题的…… class Solution {
public:int longestConsecutive(vectorint nums) {if (nums.empty())return 0;int ans 1, len 0;sort(nums.begin(), nums.end());for (int i 1; i nums.size(); i) {if (nums[i] nums[i - 1]) // 改进去重的过程continue;if (nums[i] nums[i - 1] 1) {len;} else {if (len 0) {continue;} else {ans max(ans, len 1);len 0;}}}// 进行到最后一个字符的时会出现统计疏漏需要特别判断一下if (len ! 0) {ans max(ans, len 1);len 0;}return ans;}
}; 参考 力扣
