给定一个未排序的整数数组nums找出数字连续的最长序列不要求序列元素在原数组中连续的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。示例 1输入nums [100,4,200,1,3,2] 输出4 解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2输入nums [0,3,7,2,5,8,4,6,0,1] 输出9示例 3输入nums [1,0,1,2] 输出3方法1快排1、使用sort函数对nums进行排序(默认升序)nlogn。2、循环nums向量下标定义为i定义连续长度变量为k1和最大长度max_k判断nums[i]和nums[i1]是否连续。3、假如前后两个数字连续k1并且判断k是否大于max_k更新max_k。4、假如前后两个数字相等直接跳过本次循环。5、如果两个数字不连续更新k为14、持续循环nums向量直到结束返回max_k。class Solution { public: int longestConsecutive(vectorint nums) { //集合 int nnums.size(); if(n2) return n; unordered_setint mset; for(int i0;in;i){ mset.insert(nums[i]); } int k1; int max_kk; for(unordered_setint::iterator itmset.begin();it!mset.end();it){ if(mset.find(*it-1)mset.end()){ int num*it; while(1){ if(mset.find(num1)!mset.end()){ k; max_kmax_kk?max_k:k; num; }else{ k1; break; } } } } return max_k; } };方法2哈希查找1、创建一个set集合unordered_setintm_set定义连续的长度为k,最大长度为max_k。2、将nums的数全部插入m_set中。3、循环m_set容器的值定义每个值为it。4、在m_set容器中查找it的连续数字每找到一个k1更新max_k。5、循环结束 返回 max_k。该方法在最坏的情况下还是会达到O(n^2)的复杂度//假如有一个连续序列{987654321} 那么一次枚举都要从最大的那个数开始枚举最坏的情况时间复杂度O(n^2)优化方法//如果已知有一个 x,x1,x2,⋯,xy 的连续序列 而我们却重新从 x1x2 或者是 xy 处开始尝试匹配 那么得到的结果肯定不会优于枚举 x 为起点的答案 因此我们在外层循环的时候碰到这种情况跳过即可。 //由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1 的 不然按照上面的分析我们会从 x−1 开始尝试匹配 因此我们每次在哈希表中检查是否存在 x−1 即能判断是否需要跳过了。class Solution { public: int longestConsecutive(vectorint nums) { //集合 int nnums.size(); if(n2) return n; unordered_setint mset; for(int i0;in;i){ mset.insert(nums[i]); } int k1; int max_kk; for(unordered_setint::iterator itmset.begin();it!mset.end();it){ if(mset.find(*it-1)mset.end()){ int num*it; while(1){ if(mset.find(num1)!mset.end()){ k; max_kmax_kk?max_k:k; num; }else{ k1; break; } } } } return max_k; } };unordered_set常见函数函数作用std::unordered_setint uset;构造函数std::unordered_setint uset;插入元素uset.find(10);查找元素返回一个迭代器uset.erase(10);删除元素size_t size uset.size();返回容器的大小bool isEmpty uset.empty();判断容器是否为空uset.clear();清空容器
