2021, 桃園林口三井

找第 k 大的數字 findKthLargest

不太愛解題之隨手記錄

Kth Largest Element in an Array - LeetCode

最簡單就是排序後找 k-th O(nlogn)

另一種想法是一個團體內，找年紀最大的，隨便拉一位以它為中央伍，問他比他大的分一群，小的也一群，從大群中繼續找，直到分不出群來。

k-th 也類似，就這個大群這個大小範圍內找，如果超出大群就去小群裡找

k - 大群量，得到一個新的 k' 到小群內找

• 大群 mid ≤ num
• 小群 num < mid

角落問題：如果碰巧分不出群來，就再找另一位中央伍，中央伍一定要跟別人不一樣才能分出群

直到分群剩下 1 個就是答案了。

空間可以改善的部分是 in-place ，是利用原本的 nums 置換，接著傳遞群邊界。也就是 quick select (quick sort) 技巧且降時間複雜度

分三群，中央伍群，這樣好處是如果是落在中央伍群就可以離開了

• 大群: mid < num
• 中央群: mid == num
• 小群: num < mid

網路上還有其他解法，像是 Heap (Priority Queue) ，有興趣可以看看。