K-я порядковая статистика

Дан массив nums и число k (1-индексация). Верните k-й по величине элемент, если бы массив был отсортирован по возрастанию. Полная сортировка работает и укладывается в лимиты, но подумайте, как получить ответ за O(n) в среднем (алгоритм quickselect: разбиение Хоара вокруг случайного опорного элемента, рекурсия только в нужную половину).