128. 最长连续序列 (Python3)

Problem: 128. 最长连续序列

思路

参考：

• https://leetcode.cn/problems/longest-consecutive-sequence/solutions/276931/zui-chang-lian-xu-xu-lie-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked

• https://leetcode.cn/problems/longest-consecutive-sequence/solutions/2362995/javapython3cha-xi-biao-ding-wei-mei-ge-l-xk4c/?envType=study-plan-v2&envId=top-100-liked

解题方法

1. 使用set()构建 hash table，并非总是依赖 dict，应该根据实际选取；

2. set 天然的适合去重，这道题认识到去重是很重要的；

3. 如何判断一个子序列首部？num-1 不在 set 里！

4. 如何判断一个子序列尾部？num+1 不在 set 里！

额外讨论（来自 GPT）

1 python中使用set()构建hash table

In Python, a set is implemented using a hash table. This is why sets have very efficient performance characteristics for certain operations, especially for checking membership, adding elements, and removing elements. Here’s a brief overview of how this works:

1. Hash Table Mechanism:

• A hash table is a data structure that uses a hash function to map values (keys) to positions in an array.

• In the case of a Python set, the elements of the set are the keys in the underlying hash table.

2. Efficient Operations:

• Membership Testing: Checking whether an item is in the set (x in my_set) is very fast because it uses the hash of the item to directly find the corresponding bucket in the hash table. This operation is typically O(1), meaning its execution time is constant and does not depend on the size of the set.

• Adding Elements: Adding an element to a set (my_set.add(x)) involves calculating the hash of the element and then placing it in the corresponding bucket. This is also typically an O(1) operation.

• Removing Elements: Similarly, removing an element (my_set.remove(x)) involves finding the element using its hash and then removing it from the table, which is again typically O(1).

3. Uniqueness and Hashing:

• Sets automatically ensure that they contain unique elements. When you try to add an element to a set, the set checks if the element already exists using its hash. If the element (or more precisely, an element with the same hash) is already present, the set does not add it again.

• This is why sets do not maintain the order of elements - the position of an element in the underlying array depends on its hash, not on the order in which it was added.

4. Limitations:

• Elements in a set must be hashable, which means they must be immutable (or at least, their hash value should not change over time). This is why you cannot put lists or dictionaries (which are mutable) into a set, but you can put tuples (which are immutable).

In summary, the efficiency of Python sets for certain operations is due to their implementation using a hash table, which allows for constant-time complexity for key operations like membership testing, addition, and removal.

2 Nested Loop为什么时间复杂度还是$O(N)$

To analyze the time complexity of this code, let’s look at each significant part:

1. Creating the Set (set(nums)):

• Constructing a set from the list nums has a time complexity of O(N), where N is the number of elements in nums. This step involves iterating over all elements in nums and adding them to the set, with each insertion having an average time complexity of O(1).

2. Iterating Over the Set (for num in set_nums):

• The for loop iterates over each element in set_nums. In the worst case, it will iterate N times (once for each unique element in nums).

3. Checking and Extending Sequences:

• For each num, the code checks if num - 1 is not in set_nums. This check is O(1) due to the hash table nature of sets.

• The inner while loop (while num + 1 in set_nums) checks for consecutive numbers starting from num. This might seem like it could add significant complexity, but it’s important to realize that each element from the original list is part of at most one consecutive sequence. Once a number has been used in a sequence, it won’t be the start point for another sequence check. Therefore, every number in nums contributes to this part of the algorithm at most once.

Given this, the time complexity of the entire algorithm is O(N). Here’s why:

• Even though there are nested loops, the inner while loop does not result in a complexity of O(N^2) because each number in nums is processed only once in terms of extending the sequence. Once a number has been included in a sequence, it won’t trigger the sequence extension again.

• The set construction and the loop iterations combined result in an overall linear complexity relative to the size of the input list.

So, the time complexity of the longestConsecutive method is O(N), making it an efficient solution for the problem.

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        
        # hashtab = {} 
        # python的散列表并不总是依赖dict, set也是一种 hash table，在需要去重的情况下，set更为合适！

        set_nums = set(nums) # 构建 set，去重

        len_max = 0 # 初始化一个最大长度变量，用于后续更新

        for num in set_nums: 

            # 如果 num - 1 不在 set_nums 中，那 current num 可以作为连续子序列的首部
            if num - 1 not in set_nums:
                len_seq = 1

                # 如果 num + 1 不在 set_nums 中，那就达到了连续子序列的尾巴
                while num + 1 in set_nums: # 以 current num 进行枚举
                    len_seq += 1
                    num += 1 

                # 更新最大长度变量
                len_max = max(len_max, len_seq)
        
        return len_max