输出含重复次数最多元素的子数组：求更优实现方案

Hey there! Let's break down how to level up the solution for this problem. First, let's recap the core requirement: we need to extract the subarray that includes all occurrences of the element(s) with the highest frequency in the input sequence. The basic approach works, but we can make it more efficient and robust.

What's Limiting the Basic Approach? #

The initial idea (find the most frequent element, then grab the subarray from its first to last occurrence) gets the job done for single max-frequency elements, but it has two key gaps:

1. Multiple Passes: It typically requires at least two full traversals of the array (one to count frequencies, another to find first/last indices) — we can streamline this into a single pass.
2. Tie Handling: If multiple elements share the highest frequency, we need to pick the shortest valid subarray (since all such subarrays include all their respective max-frequency elements, the shortest one is the most precise choice).

Optimized Single-Pass Approach #

This method handles everything in one traversal, giving us O(n) time complexity and O(k) space (where k is the number of unique elements in the input):

Key Steps to Implement: #

As we iterate through the array, we'll track these critical pieces of data:

• A frequency map (freq) to count how many times each element appears.
• A first_occurrence map to store the first index where each element is seen.
• Variables to track the current maximum frequency (max_freq), plus the start and end indices of the best subarray we've found so far (best_start, best_end).

For each element at index i:

1. If it's the first time we encounter the element, record its index in first_occurrence.
2. Increment its count in the frequency map.
3. Compare its frequency to max_freq:
   • If it's higher: This element becomes the new most frequent. Update max_freq, set best_start to its first occurrence index, and best_end to the current index.
   • If it's equal: Calculate the length of the subarray for this element. If this length is shorter than the current best subarray, update best_start and best_end to use this element's first and current index (this handles ties by picking the shortest valid subarray).

Example Walkthrough #

Let's test this logic against your examples:

Input 1: 1 2 3 4 1 3 4 5 6 1 4 5 6 2 1 2

• As we iterate, 1 reaches a frequency of 4 (the highest). best_start is set to 0 (first occurrence of 1), best_end to 14 (last occurrence of 1). The resulting subarray matches your expected output.

Input 2: 2 3 4 2 2 1 3 4 5 6 7

• 2 hits a frequency of 3 (max). best_start is 0, best_end is 4. The subarray from 0 to 4 is exactly the expected output.

Code Snippet (Python) #

Here's how this looks in practice:

def find_best_subarray(arr):
    freq = {}
    first_occurrence = {}
    max_freq = 0
    best_start = 0
    best_end = 0

    for i, num in enumerate(arr):
        if num not in first_occurrence:
            first_occurrence[num] = i
        freq[num] = freq.get(num, 0) + 1

        # Update max frequency and best subarray
        if freq[num] > max_freq:
            max_freq = freq[num]
            best_start = first_occurrence[num]
            best_end = i
        elif freq[num] == max_freq:
            # Check if current subarray is shorter than the best one
            current_length = i - first_occurrence[num] + 1
            best_length = best_end - best_start + 1
            if current_length < best_length:
                best_start = first_occurrence[num]
                best_end = i

    return arr[best_start:best_end+1]

# Test the examples
print(find_best_subarray([1,2,3,4,1,3,4,5,6,1,4,5,6,2,1,2]))
# Output: [1, 2, 3, 4, 1, 3, 4, 5, 6, 1, 4, 5, 6, 2, 1]

print(find_best_subarray([2,3,4,2,2,1,3,4,5,6,7]))
# Output: [2, 3, 4, 2, 2]

Why This is Better #

• Efficiency: A single pass minimizes iterations, making it faster for large datasets.
• Robustness: It handles tie cases gracefully by selecting the shortest valid subarray when multiple elements have the same highest frequency.
• Clarity: All logic is contained in one loop, making the code easier to follow and maintain.

内容的提问来源于stack exchange，提问作者Deepu--Java