初学者挑战：确认求数组众数的算法时间复杂度是否为O(n)

Hey there! Great question—let's break down how to verify if your implementation hits that O(n) time complexity mark for finding the mode (with the tiebreaker of choosing the smaller number when frequencies are equal).

First, let's align on the core requirements to make sure we're on the same page:

• Find the integer that appears most frequently in an array.
• If multiple integers share the highest frequency, pick the smallest one.
• Avoid O(n log n) approaches (like sorting-based solutions) and stick to linear time.

How a Valid O(n) Implementation Works #

A proper linear-time solution relies on two distinct linear passes:

1. Count frequencies with a hash map: Traverse the array once, using a hash map (like a Python dictionary or Java HashMap) to track how many times each number appears. Each insertion/lookup in the hash map is average O(1), so this step is strictly O(n).
2. Find the mode from the frequency map: Traverse the hash map once to identify the number with the highest frequency. When you encounter a number with the same frequency as your current candidate, update the candidate to the smaller number. Since the number of unique elements is at most n, this step is O(n) in the worst case (but often smaller in practice).

Adding these two steps together gives us O(n + k) where k is the count of unique elements. Since k ≤ n, this simplifies to O(n) time complexity.

Example Implementation #

Here's a concrete Python example to illustrate this approach:

def find_mode(arr):
    frequency = {}
    # First pass: count each number's occurrence
    for num in arr:
        frequency[num] = frequency.get(num, 0) + 1
    
    max_freq = -1
    mode = float('inf')
    # Second pass: determine the mode with tiebreaker
    for num, freq in frequency.items():
        if freq > max_freq:
            max_freq = freq
            mode = num
        elif freq == max_freq:
            if num < mode:
                mode = num
    return mode

Verifying Your Implementation #

If your code follows this pattern—no sorting, no nested loops, just two separate linear traversals—then it's definitely running in O(n) time. The key checks are:

• You're not using any operations that scale with n log n (like sorting the array).
• All hash map operations are average O(1) (which is standard for most language implementations).

Even in the worst case where every element is unique, the hash map traversal is still O(n), so the total time remains linear.

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