mirror of
https://github.com/krahets/hello-algo.git
synced 2026-07-20 10:36:09 +00:00
Yudong Jin
b01036b09e
* Update giscus scroller. * Refine English docs and landing page * Sync the headings. * Update landing pages. * Update the avatar * Update Acknowledgements * Update landing pages. * Update contributors. * Update * Fix the formula formatting. * Fix the glossary. * Chapter 6. Hashing * Remove Chinese chars. * Fix headings. * Update giscus themes. * fallback to default giscus theme to solve 429 many requests error. * Add borders for callouts. * docs: sync character encoding translations * Update landing page media layout and i18n
74 lines
2.9 KiB
Markdown
74 lines
2.9 KiB
Markdown
# Top-k Problem
|
|
|
|
!!! question
|
|
|
|
Given an unordered array `nums` of length $n$, return the largest $k$ elements in the array.
|
|
|
|
For this problem, we will first introduce two relatively straightforward solutions, followed by a more efficient heap-based solution.
|
|
|
|
## Method 1: Iterative Selection
|
|
|
|
We can perform $k$ rounds of traversal as shown in the figure below, extracting the $1^{st}$, $2^{nd}$, $\dots$, $k^{th}$ largest elements in each round, with a time complexity of $O(nk)$.
|
|
|
|
This method is only suitable when $k \ll n$, because when $k$ is close to $n$, the time complexity approaches $O(n^2)$, making it very inefficient.
|
|
|
|
|
|
|
|
!!! tip
|
|
|
|
When $k = n$, we can obtain a complete sorted sequence, which is equivalent to the "selection sort" algorithm.
|
|
|
|
## Method 2: Sorting
|
|
|
|
As shown in the figure below, we can first sort the array `nums`, then return the rightmost $k$ elements, with a time complexity of $O(n \log n)$.
|
|
|
|
Clearly, this method does more work than necessary, because we only need to find the largest $k$ elements rather than sort the other elements.
|
|
|
|
|
|
|
|
## Method 3: Heap
|
|
|
|
We can solve the Top-k problem more efficiently with a heap, as shown in the figure below.
|
|
|
|
1. Initialize a min heap, where the heap top element is the smallest.
|
|
2. First, insert the first $k$ elements of the array into the heap in sequence.
|
|
3. Starting from the $(k + 1)^{th}$ element, if the current element is greater than the heap top element, remove the heap top element and insert the current element into the heap.
|
|
4. After traversal is complete, the heap contains the largest $k$ elements.
|
|
|
|
=== "<1>"
|
|
|
|
|
|
=== "<2>"
|
|
|
|
|
|
=== "<3>"
|
|
|
|
|
|
=== "<4>"
|
|
|
|
|
|
=== "<5>"
|
|
|
|
|
|
=== "<6>"
|
|
|
|
|
|
=== "<7>"
|
|
|
|
|
|
=== "<8>"
|
|
|
|
|
|
=== "<9>"
|
|
|
|
|
|
Example code is as follows:
|
|
|
|
```src
|
|
[file]{top_k}-[class]{}-[func]{top_k_heap}
|
|
```
|
|
|
|
A total of $n$ rounds of heap insertions and removals are performed, with the heap's maximum length being $k$, so the time complexity is $O(n \log k)$. This method is very efficient; when $k$ is small, the time complexity approaches $O(n)$; when $k$ is large, the time complexity does not exceed $O(n \log n)$.
|
|
|
|
Additionally, this method is well suited to dynamic data streams. As new data arrives, we can continuously maintain the elements in the heap, enabling dynamic updates to the largest $k$ elements.
|