LeetCode 128：最优时间复杂度解法超时及算法效率疑问

给定未排序的整数数组nums，返回最长连续元素序列的长度。
你必须设计一个时间复杂度为O(n)的算法。

示例1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长连续元素序列是[1,2,3,4]，长度为4。

约束条件：

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

解题尝试过程 #

第一次尝试：排序后计数 #

我最先采用排序后遍历计数的方法，时间复杂度为O(nlogn)，但提交后意外拿到93.93%的时间百分位，耗时40ms。

第二次尝试：超时的O(n)解法 #

重新审题后，我意识到必须实现O(n)时间复杂度的解法，写出以下代码：

def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        longest_streak = 0
        
        for num in nums:
            if (num - 1) not in s:
                current_streak = 1
                while (num + 1) in s:
                    num += 1
                    current_streak += 1
                longest_streak = max(longest_streak, current_streak)
            
        return longest_streak

（我知道嵌套循环中重用num变量不是好实践，但测试过使用单独变量结果一致，这与超时问题无关）

理论上该解法时间复杂度为O(n)，应该比排序解法更快，但实际提交后在部分测试用例中超时，被驳回。

第三次尝试：通过的O(n)解法 #

参考官方解法后，我提交了能通过的代码：

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        longest_streak = 0
        
        for num in nums:
            if (num - 1) not in nums:
                next_num = num + 1
                while next_num in nums:
                    next_num += 1
                longest_streak = max(longest_streak, next_num - num)
            
        return longest_streak

我发现两段代码的关键差异：

1. 将nums原地重新赋值为集合，而非使用新变量s
2. 使用next_num变量替代current_streak计数变量

但这两处改动看似不会对运行效率产生足以让代码从超时变为通过的显著影响。更令我困惑的是，这个O(n)解法的性能仍不如排序解法，仅获得75.73%的时间百分位，耗时46ms。

疑问 #

1. 为什么O(nlogn)的排序算法实际运行起来比O(n)的算法更快？
2. 为什么我的第一个O(n)算法会超时，而改动极小的第二个O(n)算法却能通过？

内容的提问来源于stack exchange，提问作者Samson