# 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](https://longxingtan.gitbook.io/mle-interview/01_leetcode/06_heap/378.-kth-smallest-element-in-a-sorted-matrix)

[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
```