The array A is not sorted and has n distinct integer elements. Our aim to find k<=n elements that are closest to the median of this array. The distance is in terms of absolute value of the element and median's difference. The algorithm asked must have O(n) complexity.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.04.2024 11:52:28 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Let's say the range of elements is 1 to X. Then take an array of size X and store the counts of elements of this array. As all elements have count 1, the middle marked element is the median. Now loop k/2 to the left and right side of this median index. Complexity: O(n) for storing counts, then O(n) for looping k/2 on both sides, hence overall complexity is O(n).
First find the median using nth_element. Then replace each value V by |V-median|. Call again nth_element for the k-th largest new value, let's denote it by X. Now you can identify the wanted elements — those for which the new value is <= X.
How does the nth_element work in O(n)?
It's amortised complexity. It works just like quick sort, but you only call the function recursively on the half that contains your element, instead of both halves.