Нахождение k-го элемента в несортированном массиве с использованием внешней функции

Мне нужно разработать алгоритм, который находит k-й наименьший элемент в несортированном массиве, используя функцию, которая называется "MED3": эта функция находит элементы массива n/3 (floor) и 2n/3 (ceil), если он был отсортирован (очень похоже на медиану, но вместо n/2 возвращает эти значения).

Я думал о виде разбиения вокруг этих двух значений, а затем продолжить как QuickSelect, но проблема в том, что "MED3" не возвращает индексы двух значений, только значения.

например, если массив: 1, 2, 10, 1, 7, 6, 3, 4, 4, он возвращает 2 (значение n / 3) и 4 (значение 2n / 3).

Я также подумал о том, чтобы запустить массив и перевести все значения от 2 до 4 (например, в указанном выше массиве) в новый массив, а затем снова использовать "MED3", но его можно дублировать (если массив равен 2, 2, 2, 2,..., 2 Я бы взял все элементы каждый раз).

Есть идеи? Я должен использовать "MED3". * MED3 похож на черный ящик, он работает за линейное время.

Спасибо.

1 ответ

Решение

Я думаю, что вы на правильном пути, но вместо 2-4 я бы предложил удалить первые значения n/3, которые являются <= MED3.floor(), и первые значения n/3, которые>= MED3.ceil(). Это позволяет избежать проблем со слишком большим количеством дубликатов. Если два прохода / цикл не слишком дороги, вы можете удалить все значения

затем повторяйте, пока не окажетесь у k-й самой маленькой цели.

Другие вопросы по тегам