45. ソートしてない配列にてK番目に大きい要素を見つける

あるソートしていなくて、重複要素がある整数配列の、K番目大きい数字を返してください。

まずソートすると考えちゃうかもしれませんが、ソートすることでO(nlogn)がかかるので、もっといい方法ありますか？

Quick Sort と Priority Queueを振り返ると良いかも。