快速查找数组中连续重复次数最多元素及其起止索引

Solving this efficiently means traversing the array exactly once (O(n) time complexity)—no nested loops needed. Here's a straightforward implementation that tracks both the current streak and the best streak we've found so far:

Code Implementation (Python) #

def find_longest_consecutive(arr):
    if not arr:
        return None  # Handle empty array case
    
    # Initialize tracking variables for the best streak found
    best_element = arr[0]
    best_start = 0
    best_end = 0
    best_count = 1
    
    # Initialize tracking variables for the current streak
    current_element = arr[0]
    current_start = 0
    current_count = 1
    
    for i in range(1, len(arr)):
        if arr[i] == current_element:
            # Continue the current streak
            current_count += 1
        else:
            # Compare current streak to the best one
            if current_count > best_count:
                best_element = current_element
                best_start = current_start
                best_end = i - 1  # Previous index was the end of the streak
                best_count = current_count
            # Reset for the new element's streak
            current_element = arr[i]
            current_start = i
            current_count = 1
    
    # Don't forget to check the last streak after the loop ends!
    if current_count > best_count:
        best_element = current_element
        best_start = current_start
        best_end = len(arr) - 1
        best_count = current_count
    
    return {
        'element': best_element,
        'start_index': best_start,
        'end_index': best_end,
        'consecutive_count': best_count
    }

How This Works #

Let’s break down the logic in plain terms:

• Start with the first element: We initialize both our current and best streaks using the first element of the array.
• Loop through the rest: For each subsequent element:
  • If it matches the current streak’s element, we just extend the current streak count.
  • If it doesn’t match, we compare the current streak to our best streak. If the current one is longer, we update our best streak values. Then we reset the current streak to start tracking the new element.
• Final check: After the loop finishes, we have to compare the last streak (since it never got checked inside the loop) to make sure we don’t miss the longest streak if it’s at the end of the array.
• Return results: We send back a dictionary with the element, its start/end indices, and how many times it repeated consecutively.

Test Your Example Arrays #

Let’s run this function against your provided arrays to see it in action:

First Example #

arr1 = [1,5,3,3,4,4,4,5,6,6,6,6,8,9,1,1,5]
print(find_longest_consecutive(arr1))
# Output: {'element': 6, 'start_index': 8, 'end_index': 11, 'consecutive_count': 4}

This correctly identifies that 6 repeats 4 times in a row from index 8 to 11.

Second Example #

arr2 = [10,11,10,10,11,10,15,16,20,21,22,21,21,20,20]
print(find_longest_consecutive(arr2))
# Output: {'element': 10, 'start_index': 2, 'end_index': 3, 'consecutive_count': 2}

Here, multiple elements have a maximum consecutive count of 2. The function returns the first occurrence of this streak (10 from index 2 to 3). If you want to collect all streaks with the maximum count instead of just the first, you can modify the function to store a list of results instead of a single entry.

Edge Cases Handled #

• Empty array: Returns None (adjust this to return a custom message if needed).
• Single element: Returns that element with start/end index 0 and count 1.
• All elements identical: Returns the element with start index 0, end index equal to the array length minus 1, and count equal to the array length.
• Longest streak at the end: The final post-loop check ensures this is captured correctly.

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