Kth Largest Element in an Array - LeetCode
Note that in the interview settings, not all the constraints may be given to you upfront. The interviewer may have simply forgotten to fully specify them, or they may be evaluating whether you are thinking about those carefully. Here are some strategies for answering the question.
A quick sanity check of the algorithm is to try it on extreme cases: k=1, k=n. If any of these two cases gives you an O(n^2) runtime, then you know it’s not correct.
When you ask for a hint, the interviewer will most likely mention the quicksort algorithm as a reference. Make sure to understand how the quicksort algorithm works and be ready to explain it in detail.
The key insight is that, unlike in quicksort, once we determine the position for the pivot element, we don’t need to sort both sides of the pivot, and only focus on one side where it’s guaranteed to contain the answer.
Time complexity analysis will be tricky, as the worst case performance may be quadratic. A simple shuffle of the array in the beginning, or randomly choosing the pivot element will allow you to analyze just the average time complexity. The gist of the analysis is:
もし配列がソートされているのであればnums[k]を返せば良い。 ソートするのにO(nlogn) これがベースとなるアルゴリズム。 でもこれじゃストレートすぎる。もっと良い計算量でやろう。
よくあるデータ構造で数列の順序情報を含むものがないか考えてみる。すると、min-heapを使うことを思い出します。min-heapは、親ノードが子ノードよりも小さいか同じであるバイナリツリーです。Pythonでは、heapqライブラリを使用して簡単に実装できます。配列の最初のk要素をヒープに追加し、残りの各要素について、それがヒープの最小要素（つまり、ヒープのルート）よりも大きい場合、最小要素を削除して新しい要素を追加します。これにより、ヒープが常にこれまでに見たk個の最大要素を含むことが保証されます。ヒープの最小要素は、配列のk番目に大きい要素です。
この解答は、配列の長さであるnに対してO（n log k）の時間で動作します。ヒープを保存するための空間計算量はO（k）です。これは、O（n log n）の時間がかかる配列のソートよりも効率的です。
ではこれでいいのかというと、あと一歩。ここで面接官がヒントとしてクイックセレクトを言うかもしれない。
まず、Quickselectアルゴリズムがどのように機能するかを理解します。
次に、このアルゴリズムをPythonで実装する方法を説明します：
import random
def findKthLargest(nums, k):
# k番目に大きい要素をk番目に小さい要素に変換します
return quickselect(nums, len(nums)-k)
def quickselect(nums, k):
pivot = random.choice(nums)
left = [x for x in nums if x < pivot]
right = [x for x in nums if x > pivot]
mid = [x for x in nums if x == pivot]
L, M = len(left), len(mid)
if k < L:
# kが左部分の長さ（ピボットのインデックス）より小さい場合、k番目に大きい要素は左部分にあります。
return quickselect(left, k)
elif k < L + M:
# kが左部分の長さと中部分の長さの合計より小さい場合、k番目に大きい要素はピボットです。
return nums[k]
else:
# kが左部分の長さ＋中部分の長さより大きい場合、k番目に大きい要素は右部分にあります。
return quickselect(right, k-L-M)
上記のコードでは、quickselect関数を使ってk番目に小さい要素を見つけます。ランダムにピボットを選ぶことで時間の複雑さを最適化します。パーティションの過程は3つのステップで行われ、ピボットより小さい要素、等しい要素、大きい要素のリストを作成します。その後、kが"mid"リストの範囲にあるかどうかをチェックします。もし範囲にない場合、"left"リストまたは"right"リストでプロセスを繰り返します。
面接本番では、すべての制約が最初から与えられるわけではないことに注意してください。面接官は完全に指定し忘れた可能性があるだけでなく、あなたがそれらについて注意深く考えているかどうかを評価しているかもしれません。以下は、質問に答えるためのいくつかの戦略です。