古典的なアルゴリズム: 順序付けられていない配列の K 番目に大きい値を見つける

[[409182]]

1. K番目に大きいものを見つける

タイトル

順序付けられていない整数配列があります。ソートの考え方に基づいて、配列内の K 番目に大きい数値を見つけてください。

整数配列 a が与えられた場合、K 番目 (1<=K<=n) の最大の数値 (重複要素を含むが、重複を削除する必要はない) を返し、答えが存在することを確認します。

例

[3, 2, 1, 5, 6, 4] 、2を入力
戻り値5

2. 従来の考え方

まず順序付けられていない配列をソートし、次に順序付けられた配列を検索します。

どのソートアルゴリズムを選択するかは、まだ決まっていません。

まず、さまざまなソートアルゴリズムの複雑さと安定性を見てみましょう。

上記の比較を読んだ後、あなたはすでに自分の答えを頭の中で持っているかもしれません。

3. 問題解決のアイデア

従来の考え方には 2 つのステップが必要です。

まず全体を並べ替える
注文の目標値を見つける

それで、この質問では、ソート処理中に目標値を決定できるのでしょうか?

クイックソートのバイナリ特性を考慮してください。

まず、左側がそれ自体より小さく、右側がそれ自体より大きい値の位置を見つけます（配列全体が2つに分割されます）
次に、配列全体が整うまで、左側と右側の部分でそれぞれ手順 1 を繰り返します。

ここで知っておく必要があるのは、クイックソートでは、左側の値がそれ自体よりも小さく、右側の値がそれ自体よりも大きいということです。この値の位置は、最終的な順序付けられた配列内の位置であり、検索中にターゲットの位置を決定できることを意味します。さらに、この問題を処理する過程では、平均してデータ量の半分だけが処理されます。

アニメーション - クイックソートアルゴリズム

クイックソートアルゴリズムの検索プロセス:

4. Goコードの実装

func findKLargest(arr [] int , k int ) int {
    len(arr) == 0 || k > len(arr) の場合 {
 -1を返す
    } 
 
    var find func(k int , l, r int ) int  
    find = func(k int , l, r int ) int {
        /*
        // 通常のクイックソートには次のコードが必要です
        l >= r の場合 {
戻る 
        }
        // しかし、ここでは必要ありません。k番目に大きいデータを探す場合、通常はl==rです。
        */
        ll := l
        rr := r
        ターゲット := arr[l] 
 
        // 逆順（K番目によく使われる）は target >= arr[r] / target <= arr[l] です
        // 正の順序（k番目に使用頻度が低い）は target <= arr[r] / target >= arr[l] です
l < r {の場合
l < r && ターゲット >= arr[r] {
                r --  
            }
            arr[l] = arr[r] 
 
 l < r && ターゲット <= arr[l] {
                l++
            }
            arr[r] = arr[l]
        } 
       
        arr[l] = ターゲット
        // k は l の右側にあります
        // 次のコードでは、左側でも右側でも、最初のパラメーターが k なのはなぜですか?
        // k は検索する値の添え字位置を参照するため (k 番目に大きい値は添え字 k-1 になります)
        // 配列 arr の左側または右側に関係なく、対応する添え字は固定です
        // l/r は毎回変わるので、k はここで固定されます
        k > l の場合 {
            // ここでl+1、rrは配列の添え字でもある
find(k, l+1, rr)を返す
        }そうでなければk<l{
            // k は l の左側にあります
            // ここでもll、l-1は配列の添え字です
find(k, ll, l-1)を返す
        } 
 
        // この時点で、位置lのターゲットはk番目に大きい値です
リターンターゲット
    } 
 
    // ソート後の k 番目に大きい値は配列インデックス k-1 です
    見つける:= find(k-1, 0, len(arr)-1) 
 
リターン検索
}