これはインタビューの質問で、私の分析が正しかったかどうか疑問に思っています。
「マジック選択」関数は、基本的に、サイズが n の配列で「m 番目」の最小値を生成します。タスクは、効率的なアルゴリズムを使用して「m」要素を昇順にソートすることでした。私の分析は、最初に「マジックセレクト」機能を使用して「m番目」の最小値を取得することでした。次に、パーティション関数を使用してピボットを作成し、左側の小さな要素をすべて取得しました。その時点で、左半分を効率的にソートするタスクをバケット ソートで実行する必要があると感じました。
これが「m」個の最小要素をソートする最良の方法であるかどうか疑問に思っていました。ここでもクイックソートが使用される可能性があります。ただし、比較ベースの並べ替えを回避すると、O(n) が発生する可能性があると考えました。これにも基数ソートまたはヒープソート (O(nlogn)) を使用できますか? 可能な限り最良の方法でそれをしなかった場合、これを達成するための最良の方法はどれですか? 使用を許可されたデータ構造は配列でした。
どうもありがとう！