> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/00_array/215.-kth-largest-element.md).

# 215. Kth Largest Element

<https://leetcode.com/problems/kth-largest-element-in-an-array/>

## solution

<https://www.geeksforgeeks.org/kth-smallest-largest-element-in-unsorted-array/>

* 直接法

```python
# 不满足O(n)题目要求
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[-k]
```

时间复杂度：O(nlogn)\
空间复杂度：O(1)

* heap/ priority queue
  * 寻找第k大的, 也就是堆里要保留前k大, 把较小的pop出去, 因此用小顶堆, python支持小顶堆.
  * 寻找第k小的, 就要用大顶堆, python取负数

```python
# 大顶堆和小顶堆都能实现, 但复杂度不一样，nlogn 或 nlogk

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heapq.heappush(heap, num)

            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]
```

时间复杂度：O(nlog(k))\
空间复杂度：O(k)

* quick sort/ quick select
  * Quick Select 的时间复杂度会退化为 O(n^2), 优化方法: 随机pivot, 三数取中法（Median of Medians）

```python
def partition(nums, l, r, pivot_index):
    # build-in change the nums, and return the position
    # l含义: 第一个比pivot大的位置
    pivot = nums[pivot_index]
    nums[pivot_index], nums[r] = nums[r], nums[pivot_index]
    i = l
    for j in range(l, r):
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    nums[i], nums[r] = nums[r], nums[i]
    return i

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        l = 0
        r = len(nums) - 1
        return self.quick_select(nums, l, r, k)

    def quick_select(self, nums, l, r, k):
        while True:  # 如果只有一个元素, 确实不符合 l < r
            pivot_index = random.randint(l, r)
            pos = partition(nums, l, r, pivot_index)
            if pos == len(nums) - k:
                return nums[pos]
            elif pos > len(nums) - k:
                r = pos - 1
            else:
                l = pos + 1

    def quick_select2(self, nums, l, r, k):
        # 分治
        p = partition(nums, l, r, r)

        if p == k - 1:
          return nums[p]

        if p > k - 1:  # search lower part
          return self.quick_select2(nums, k, l, p - 1)

        # search higher part
        return self.quick_select2(nums, k, p + 1, r)
```

时间复杂度：O(n) -> O(n^2)\
空间复杂度：O(1)

* binary search

```python
def get_count(v, nums):
    count = 0
    for num in nums:
        if num <= v:
            count += 1
    return count

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        low = min(nums)
        high = max(nums)
        while low < high:
            mid = low + (high - low) // 2
            if get_count(mid, nums) <= len(nums) - k:
                low = mid + 1
            else:
                high = mid
        return low

    def findKthSmallest(self, nums: List[int], k: int) -> int:
        low = min(nums)
        high = max(nums)
        while low < high:
            mid = low + (high - low) // 2
            if get_count(mid, nums) < k:
                low = mid + 1
            else:
                high = mid
        return low
```

时间复杂度：O()\
空间复杂度：O()

* bucket sort

```python
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        count = {}
        for i in reversed(range(min(nums), max(nums)+1)):
            count[i] = 0
        for num in nums:
            count[num] += 1

        for val, f in count.items():
            if k > f:
                k-=f
                continue
            else:
                return val
```

## follow up

[373. Find K Pairs with Smallest Sums](https://leetcode.com/problems/find-k-pairs-with-smallest-sums/)

* 超时: 注意已排序

```python
class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        heap = []

        for num1 in nums1:
            for num2 in nums2:
                heapq.heappush(heap, (-num1-num2, num1, num2))
                if len(heap) > k:
                    heapq.heappop(heap)

        res = []
        for i in heap:
            res.append([i[1], i[2]])
        return res
```

```python
class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        heap = []

        for i, num1 in enumerate(nums1):
            heapq.heappush(heap, [num1+nums2[0], i, 0])

        res = []
        while heap and len(res) < k:
            sum, i, j = heapq.heappop(heap)
            res.append([nums1[i], nums2[j]])
            if j + 1 < len(nums2):
                heapq.heappush(heap, [nums1[i] + nums2[j + 1], i, j + 1])
        return res
```

时间复杂度：O(klog(k))\
空间复杂度：O(k)

[378. Kth Smallest Element in a Sorted Matrix](/mle-interview/01_leetcode/06_heap/378.-kth-smallest-element-in-a-sorted-matrix.md)

[Median of an unsorted array using Quick Select Algorithm](https://www.geeksforgeeks.org/median-of-an-unsorted-array-in-liner-time-on/)

[1985. Find the Kth Largest Integer in the Array](https://leetcode.com/problems/find-the-kth-largest-integer-in-the-array/description/)

```python
```

[703. Kth Largest Element in a Stream](https://leetcode.com/problems/kth-largest-element-in-a-stream/description/)

```python
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://longxingtan.gitbook.io/mle-interview/01_leetcode/00_array/215.-kth-largest-element.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.