К-ая порядковая статистика (k-й минимум)
Medium
Дан массив nums и k (1 <= k <= n). Вернуть k-й по возрастанию элемент (k-th smallest). Требуется O(n) в среднем (алгоритм Quickselect) или проще — сортировка O(n log n).
Примеры:
Вход:
{"nums": [3, 1, 2, 4], "k": 2}
Выход:
2
Вход:
{"nums": [1], "k": 1}
Выход:
1
Вход:
{"nums": [5, 5, 5, 5], "k": 3}
Выход:
5
Ограничения:
1 <= n <= 10^6; элементы целые; 1 <= k <= n
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!