LeetCode 筆記 - 215. Kth Largest Element in an Array

如何在無序數列中找到第 k 大的元素？本文分析了局部選擇與全局排序的效能差異。在大規模數據下，適當的排序配合索引存取往往比多次選擇更具優勢。這是一篇關於演算法選擇與數據規模權衡的實務討論。

發佈

2022.06.25

閱讀

約 1 分鐘

字數

183

⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

給定一個數列，請給出第 k 大的元素

解題思維

這題其實就是引誘你做 k 次 select

當數列很大的時候，Sorting 需要的 $O(\log n)$ 其實就會比 k 小很多

所以乖乖做個 Sorting 之後取第 k 個即可

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort(reverse=True)
        return nums[k - 1]