java - LinkedList の数値の中央値を見つける

Question

Java で LinkedList として保存されている数値のリストの中央値をどのように見つけますか? ウィキペディアで言及されている選択アルゴリズムがわかりません。それを説明できればボーナスポイント。

Answer 1

最適なアルゴリズムはQuickSelect です

記事を読んで QuickSort を理解しよう - 概念は似ています。

Answer 2

基本的に 2 つの主要なオプションがあります。

1. 簡単で迅速な方法 - でリストを並べ替えますO(nlogn)。中央値は値の半分がそれよりも大きく、半分が小さい値として定義されるため、ちょうどn/2th の値を取ります - それが中央値です。

2. これがパフォーマンス上重要なタスクである場合は、さまざまな選択アルゴリズムを適用してO(n)、適切なケースを提供できます (ただし、最悪のケースで線形性を保証することはできません)。

いずれにせよ、選択アルゴリズムに関するウィキペディアのエントリをチェックしてください。これにより、利用可能なすべての方法について適切なまとめが得られるはずです。