Условие задачи

Дан массив целых чисел 'nums' и целое число 'k'. Необходимо вернуть 'k'-ый наибольший элемент в массиве.

Для решения задачи требуется написать программу на языке Python, которая принимает на вход массив целых чисел 'nums' и число 'k', а затем возвращает 'k'-ый наибольший элемент в массиве. Обратите внимание, что это 'k'-ый наибольший элемент в отсортированном порядке, а не 'k'-ый уникальный элемент.

Примеры

Пример 1:

Input: nums = [3,2,1,5,6,4], k = 2

Output: 5

Explanation: Отсортированный массив - [1,2,3,4,5,6]. Второй наибольший элемент в массиве - 5.

Пример 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4

Output: 4

Explanation: Отсортированный массив - [1,2,2,3,3,4,5,5,6]. Четвертый наибольший элемент в массиве - 4.

Решение

Для решения задачи необходимо использовать алгоритм нахождения k-ой порядковой статистики. Этот алгоритм находит элемент, который занимает 'k'-ое место в отсортированном массиве.

Шаги алгоритма:

1. Выбрать случайный элемент из массива.
2. Разбить массив на две части: элементы меньше выбранного элемента и элементы больше или равные выбранному элементу.
3. Определить, в какой части массива находится 'k'-ый элемент.
4. Рекурсивно повторить шаги 1-3 для соответствующей части массива.

Пример

Для массива nums = [3,2,1,5,6,4] и k = 2, выберем случайный элемент, например, 4. Разобьем массив на две части: [3,2,1] и [5,6]. Определим, что 'k'-ый элемент находится во второй части, так как в первой части только 3 элемента, а 'k' равно 2. Рекурсивно повторим шаги 1-3 для массива [5,6]. Для него выберем случайный элемент, например, 5. Разобьем массив на две части: [6] и [5]. Определяем, что 'k'-ый элемент находится в первой части, так как во второй части только 1 элемент, а 'k' равно 2. Рекурсивно повторим шаги 1-3 для массива [6]. Для него выберем единственный элемент, который и будет являться 2-м по порядку в отсортированном массиве.