[解決済み】長さnのソートされていない配列の中でk番目に大きい要素をO(n)で見つけるにはどうすればよいですか？）

質問

長さnのソートされていない配列の中でk番目に大きい要素をO(n)で求める方法があると思うのですが、どうでしょうか？ というか、"expected" O(n)とかになっているのかもしれません。 どうやったらできるんでしょうか？

どのように解決するのか？

を見つけるといいます。 k次統計量 . 非常に簡単なランダム化アルゴリズム( クイックセレクト を取る) O(n) 平均時間 O(n^2) 最悪の場合の時間、そしてかなり複雑な非ランダム化アルゴリズム( イントロセレクト を取る) O(n) 最悪の場合 に情報があります。 ウィキペディア しかし、それはあまり良いものではありません。

<ストライク 必要なものはすべて このパワーポイントスライドは . の基本アルゴリズムを抽出するだけで O(n) 最悪の場合のアルゴリズム(introselect)。

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

また、Cormenらの「アルゴリズム入門」にも非常にきれいに詳しく書かれています。