K-й наименьший элемент в списке
Пусть дано
n целых чисел и число k. Требуется найти k-й наименьший элемент в списке. Гарантируется, что все элементы массива различны.Входные данные
В первой строке входных данных находятся два целых числа
n и k (1 ≤ k ≤ n ≤ ).Во второй строке задаются
n целых чисел (), разделённые пробелами.Выходные данные
Необходимо вывести значение
k-го наименьшего элемента из данного списка.Примеры
Входные данные | Выходные данные |
6 3
10 -2 4 8 3 6 | 4 |
7 2
-4 5 8 -3 10 0 7 | -3 |
Пояснение
- Отсортированный список будет выглядеть так: [-2, 3, 4, 6, 8, 10]. Следовательно, 3-й наименьший элемент равен 4.
- Отсортированный список будет выглядеть так: [-4, -3, 0, 5, 7, 8, 10]. Следовательно, 2-й наименьший элемент равен -3.
Hint 1
Используйте случайное разбиение (random partitioning), похожее на то, что применяется в алгоритме QuickSort.
Сортировка элементов может оказаться непосильной с учётом ограничений по времени.
Hint 2
Можно разбивать массив по принципу QuickSort, используя случайный опорный элемент (pivot). Затем достаточно оставить лишь ту часть массива, в которой наверняка находится искомый элемент, а остальную часть игнорировать.
Продолжайте этот процесс до тех пор, пока количество элементов, отсекаемых перед нужным элементом, не станет равно
k.Случайное разбиение даёт ожидаемую линейную сложность — вы знаете, почему?
Hint 3
При каждом случайном разбиении ожидается, что получающийся подмассив будет иметь размер примерно половины исходного. Если сейчас у нас массив размера
n, после одной операции разбиения можно отбросить половину — n/2, после следующей операции — n/4 и так далее. Суммарно получается .Однако стоит помнить, что в худшем случае (если выбор опорного элемента постоянно неудачен) алгоритм может работать за .
Constraints
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB