Поиск медианы чисел в LinkedList

Как вы находите медиану списка чисел, сохраненных как LinkedList в Java? Я не понимаю алгоритм выбора, на который ссылается Wikipedia. Бонусные баллы, если вы можете это объяснить.Поиск медианы чисел в LinkedList

источник

2009-05-17 Penchant

Возможно, ваш первый шаг должен состоять в том, чтобы скопировать данные в массив/ArrayList. –

Определенно, если вы не хотите, чтобы медиана нарушала вашу копию списка. Однако, если это только для эффективности сортировки, Collections.sort() делает это внутренне в любом случае. –

Лучший алгоритм QuickSelect

Прочитайте статью и попытаться понять QuickSort - концепция аналогична.

источник

2009-05-17 19:23:42 Dario

Но будет ли этот алгоритм по-прежнему самым быстрым в списке * связанных *? Кажется, что для маленького N наивный подход может быть лучше. –

Да, будет. QuickSelect отлично применим к связанным спискам (даже на чисто функциональных языках)! – Dario

Ссылка устарела. –

Если вы хотите быстрый способ, соберите список и выберите средний элемент (или средний из двух средних элементов).

Более эффективные алгоритмы выбора в основном стараются избегать сортировки битов списка, который вы на самом деле не нужно сортировать, чтобы найти п й элемент для вашего дал п. (The JDK настоящее время не обеспечивает такой алгоритм из коробки.) Update: просто расширить на моем предыдущем посте, примеры более эффективных методов будет включать в себя:

основывая выбор на parallel sort, начальная фаза помещает данные в ряд «ведер» перед сортировкой каждого из ковшей, но затем (в случае медианы), где вы фактически сортируете только средний ковш, так как точный порядок элементов в ведрах с обеих сторон нерелевантный
Базовый выбор по алгоритму сортировки с разделением и победой, такой как Quicksort, но опять же, где алгоритм фактически не сортирует подсписки, которые находятся за пределами требуемого диапазона.

источник

2009-05-17 19:47:43

-1

Медиана - это номер в середине отсортированного списка. (Легко для списка с нечетным количеством записей, для списка с четным количеством записей это может быть любое число между двумя «средними номерами», которые включены в комплект)

Итак, сортируйте список и выясните, среднее число (ы) есть.

источник

2009-05-17 19:56:12

Сортировка намного сложнее (O (nlogn)), чем выбор медианы (O (n)) – Dario

Будет ли QuickSelect вы защищать, а не работать в O (log n)? Если нет, почему вы говорите O (n)? –

На самом деле защитник QuickSelect, который он защищает, будет работать в O (n). Intuitiveley, он будет делать меньше работы, чем QuickSort, поскольку на каждом шаге он только продолжает смотреть на левую или правую половину массива. –

У вас есть в основном два основных варианта:

простой и быстрый способ - сортировать список в O(nlogn). Поскольку медиана определяется как значение, которое в два раза превышает его, а половина меньше, просто возьмите значение n/2 - это медиана.
Если это важная задача, вы можете применять различные алгоритмы выбора, которые могут дать вам O(n) в хороших случаях (но все же не могут гарантировать линейность в худших случаях).

В любом случае, проверьте запись википедии на Selection Algorithms, что должно дать вам хорошую облаву на все доступные методах.

источник

2009-05-17 22:22:08

Поиск медианы чисел в LinkedList

ответ

Смежные вопросы