[特殊字符]【算法日记15】LeetCode 128. 最长连续序列：排序法 vs 哈希表的底层真相

题目背景今天咱们来手撕 LeetCode 上一道极具迷惑性的经典大题[128. 最长连续序列]。 这道题不仅考察了常规的数组操作更是一块检验程序员底层功底的绝佳“试金石”题目最后还有一句灵魂要求“你必须设计并实现时间复杂度为O(n)的算法解决此问题。”【题目描述】给定一个未排序的整数数组nums找出数字连续的最长序列不要求序列元素在原数组中连续的长度。【示例】输入:nums [100, 4, 200, 1, 3, 2]输出:4解释:最长数字连续序列是[1, 2, 3, 4]。它的长度为 4。 方法一直观的排序法 (时间复杂度 O(N log N))人类最直观的思维既然要找连续的数字那把它们从小到大排个序挨个往后数不就行了【核心避坑点】空数组兜底遇到[]直接返回 0。重复数字跳过比如[1, 2, 2, 3]遇到相等的数字要直接无视不能打断连续状态。断网重连机制一旦发现数字不连续比如遇到跳跃的数字必须立刻结算当前最高纪录并将连击数清零变回 1重新开始计算。 排序法 C 代码#include iostream #include vector #include algorithm using namespace std; class Solution { public: int longestConsecutive(vectorint nums) { if(nums.empty()) return 0; sort(nums.begin(), nums.end()); int curr 1; int max_curr 1; for(int i 1; i nums.size(); i) { if(nums[i] ! nums[i-1]) { // 忽略重复元素 if(nums[i] - 1 nums[i-1]) { curr 1; // 连续连击数 1 } else { max_curr max(max_curr, curr); // 断开连续结算最高分 curr 1; // 重新开始连击 } } // 每次循环末尾稳妥更新纪录防止最长序列在末尾 max_curr max(curr, max_curr); } return max_curr; } }; 方法二哈希表的“降维打击” (时间复杂度 O(N))为了满足题目O(N)的要求我们需要放弃排序直接祭出终极大杀器哈希集合unordered_set。【核心逻辑只找排头兵】将所有数字扔进哈希表中去重并获得O(1)的查询速度。扫描数字时判断num - 1是否存在。如果存在说明它只是队伍里的小兵直接跳过只有当num - 1不存在时说明它是这支连续队伍的“开头排头兵”。此时才开启while循环顺藤摸瓜寻找num 1直到队伍结束。 哈希表法 C 代码#include iostream #include vector #include unordered_set #include algorithm using namespace std; class Solution { public: int longestConsecutive(vectorint nums) { if(nums.empty()) return 0; // 1. 数据全部丢进超级雷达哈希表 unordered_setint us(nums.begin(), nums.end()); int curr_max 0; for(auto num : us) { // 2. 只有发现“排头兵”才允许进入循环顺藤摸瓜 if(!us.count(num - 1)) { int curr_num num; int curr 1; // 3. 顺着排头兵往下找 while(us.count(curr_num 1)) { curr_num 1; curr 1; } // 4. 结算当前队伍的最高纪录 curr_max max(curr, curr_max); } } return curr_max; } }; 深度硬核解析为什么 O(N) 实际运行比 O(N log N) 慢在 LeetCode 的实际提交中你会发现一个违背直觉的现象排序法($O(N \log N)$) 耗时约14ms。哈希表法($O(N)$) 耗时高达94ms。难道理论错了吗不这是底层物理法则的限制面试大厂如果能答出以下两点直接拿满分哈希表建表的“隐藏代价”极大 C 中的sort是基于内省排序只需在连续内存中原地位移即可极其轻量。而构建unordered_set需要计算哈希值、分配内存、处理冲突。遇到哈希碰撞或需要扩容Rehash时底层会消耗大量的额外时间这个“常数代价”极其惊人。CPU 缓存未命中 (Cache Miss) 数组在内存中是连续存储的CPU 在读取当前数字时会顺手将后面的数字全部拉入高速缓存读取速度飞快而哈希表在内存中是随机分布的CPU 经常在缓存中找不到下一个节点只能被迫去慢速内存中寻址这被称作“缓存未命中”会严重拖慢运行效率。 总结理论上的最优解不一定是工程上的最快解。在数据量 $N$ 只有十万级别时哈希表的常数耗时抵消了 $O(N)$ 的优势。只有当数据量上亿$\log N$ 变得极其巨大时哈希表的碾压姿态才会显现。