To solve this problem, we need to find the length of the longest consecutive elements sequence in an unsorted list of integers, with the constraint that the algorithm runs in O(n) time.

Approach

The key insight to achieve O(n) time complexity is to use a hash set for O(1) lookups. Here's the step-by-step approach:

1. Handle Edge Case: If the input list is empty, return 0.
2. Create a Set: Convert the list into a set to eliminate duplicates and enable O(1) existence checks.
3. Find Sequence Starts: For each number in the set, check if it is the start of a consecutive sequence (i.e., the number minus 1 is not present in the set).
4. Count Sequence Length: For each valid start, count the length of the consecutive sequence by checking subsequent numbers (current number +1) in the set.
5. Track Maximum Length: Keep track of the longest sequence length encountered.

Solution Code

def longestConsecutive(nums):
    if not nums:
        return 0

    num_set = set(nums)
    max_length = 0

    for num in num_set:
        # Check if current number is the start of a sequence
        if num - 1 not in num_set:
            current_num = num
            current_length = 1

            # Extend the sequence as long as next number exists
            while current_num + 1 in num_set:
                current_num += 1
                current_length += 1

            # Update max length if current sequence is longer
            max_length = max(max_length, current_length)

    return max_length

Explanation

• Set Usage: The set allows us to quickly check if a number exists, which is crucial for O(1) lookups.
• Sequence Start Check: By checking if num-1 is not in the set, we ensure we only start counting sequences from their first element, avoiding redundant checks.
• Efficiency: Each element is processed exactly once (either as a start of a sequence or as part of an existing sequence). This ensures the overall time complexity is O(n).

Example Walkthrough

For the input list [100,4,200,1,3,2]:

1. The set becomes {100, 4, 200, 1, 3, 2}.
2. For 100: 99 not present → sequence length is 1.
3. For 4: 3 present → skip.
4. For 200: 199 not present → sequence length is1.
5. For 1: 0 not present → sequence extends to 2→3→4 → length is 4.
6. For 3: 2 present → skip.
7. For 2: 1 present → skip. The maximum length is 4, which is correct.

This approach efficiently finds the longest consecutive sequence with O(n) time and space complexity. It handles duplicates and edge cases (empty list, single element) correctly.

作者声明:本文包含人工智能生成内容。