如何设计线性时间算法找出数组中出现次数超n/k次的元素？

Hey there! Let's break down how to tackle this problem, and connect the dots with that quickselect hint you're confused about. First, let's start with a key observation that makes the whole problem manageable:

Any element that appears more than n/10 times in an array of size n can have at most 9 such elements. Why? Because 9*(n/10) < n — if there were 10 elements each appearing >n/10 times, their total count would exceed n, which is impossible.

That's the foundation. Now let's cover both the quickselect-based approach (as per the hint) and the general n/k solution you mentioned in papers.

Quickselect-Based Approach (Following the Hint) #

The hint mentions using quickselect to find the n/10-th largest key and checking its count — here's why that works:

If an element x appears more than n/10 times, then in the sorted version of the array, x must occupy at least n/10 + 1 consecutive positions. That means x will definitely be present at one of these indices: n/10, 2n/10, ..., 9n/10 (0-based or 1-based, doesn't matter as long as we're stepping by n/10).

So the steps are:

• Use quickselect 9 times to find the element at positions i*(n/10) for i from 1 to 9. Quickselect runs in O(n) time per call, and 9*O(n) is still linear time.
• For each of these 9 elements, iterate through the entire array to count how many times it appears. This is another O(n) step.
• Collect all elements whose count exceeds n/10 — these are your decimal dominants.

This works because we're only checking the elements that could possibly be dominants (since any real dominant has to show up in those quantile positions), and all steps are linear time.

General n/k Solution (Boyer-Moore Voting Algorithm Extension) #

If you're curious about the paper's general solution for elements appearing more than n/k times, it's an extension of the Boyer-Moore majority vote algorithm (which handles k=2). Here's how it works for k=10:

1. Maintain candidates: Keep track of up to 9 candidate elements and their respective counts.
2. Traverse the array:
   • If the current element is already one of the candidates, increment its count.
   • If any candidate has a count of 0, replace that candidate with the current element and set its count to 1.
   • If neither of the above, decrement the count of all candidates by 1.
3. Verify candidates: After the first pass, the candidates are just potential dominants — we need to iterate through the array again to count how many times each candidate actually appears. Only keep those with counts >n/10.

This approach is also linear time: the first traversal is O(n), and the verification pass is O(n) as well. The space complexity is O(k) (O(1) for k=10, since we only need 9 candidates).

Why Your Sorting Approach Doesn't Meet the Requirement #

Your idea of sorting then counting is correct, but sorting takes O(n log n) time, which is slower than the linear time requirement. The approaches above avoid sorting entirely, keeping the time complexity strictly linear.

Hopefully this clears up the connection between quickselect and the problem, and makes the general solution easier to follow!

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