Как и любая другая проблема выбора медианы для несортированного массива, но с дополнительным ограничением. нам необходимо использовать предоставленную подпрограмму / вспомогательную функцию Quart (A, p, r), которая находит 1/4 упорядоченного элемента в данном подрешетке за линейное время. Как мы можем использовать эту вспомогательную функцию, чтобы найти медиану массива?
Дальнейшее ограничение:
1. Ваше решение должно быть выполнено на месте (не новое
массив может быть создан). В частности, одним из альтернативных решений будет
расширить массив до размера m, чтобы все записи в A [n + 1, ..., m] =
1 и m> 2n. После этого вы сможете решить медиану
проблема в исходном массиве с одним вызовом квартили
в расширенном массиве. С дальнейшими ограничениями это невозможно.
2. во время работы алгоритма вы можете временно изменять элементы в массиве, например, SWAP меняет элементы. Но после завершения вашего алгоритма все элементы в массиве должны быть такими же, какими они были в начале (но так же, как в алгоритме рандомизированного выбора, который преподается в классе, они могут быть в другом порядке, чем они были изначально).
Поскольку вам не разрешено создавать новые массивы, это означает, что вы можете изменять только небольшое (постоянное) количество элементов.