Всем Привет!
Попалась недавно задачка, к которой не могу подобрать алгоритм. ((
Когда уже мысли кончились, решил погуглить, но решения так и не обнаружил... хотя в некоторых статьях пишут, что оно существует ))
Задача такова, что необходимо найти медиану массива (неотсортированного конечно же).
Т.е. такое значение, которое после сортировки массива A[1...n] будет равно:
элементу A[n / 2 + 1], при нечетном n и (A[n / 2] + A[n / 2 + 1]) / 2.0, при четном n.
НО.... самое интересное, что алгоритм должен быть линейным... 8)
Попалась недавно задачка, к которой не могу подобрать алгоритм. ((
Когда уже мысли кончились, решил погуглить, но решения так и не обнаружил... хотя в некоторых статьях пишут, что оно существует ))
Задача такова, что необходимо найти медиану массива (неотсортированного конечно же).
Т.е. такое значение, которое после сортировки массива A[1...n] будет равно:
элементу A[n / 2 + 1], при нечетном n и (A[n / 2] + A[n / 2 + 1]) / 2.0, при четном n.
НО.... самое интересное, что алгоритм должен быть линейным... 8)
Я решал через heap за NLogN
Считываем n/2+2 чисел.
Потом на каждом шаге добавляем текущее число и удаляем из heap самое большое из имеющихся.
Ответом будет либо 2 элемента, которые лежат на вершине или один в зависимости от чётности N.
Полностью линейное решение использует 2 прохода по входным данным.
И как реализовать полностью линейное решение в 2 прохода?
http://habrahabr.ru/post/115018/
Вы заметили, что тема была создана три года назад?)
Для меня оказалась актуальна и сейчас :)
https://habr.com/en/post/346930/