215.Kth Largest Element in an Array
===

###### tags: `Medium` `Array` `Divide and Conquer` `Sorting` `Heap`

[215. Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/)

### 題目描述

Given an integer array `nums` and an integer `k`, return *the k^th^ largest element in the array.*

Note that it is the k^th^ largest element in the sorted order, not the k^th^ distinct element.

Can you solve it without sorting?

### 範例

**Example 1:**

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

**Example 2:**

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

**Constraints**:

* 1 <= `k` <= `nums.length` <= 10^5^
* -10^4^ <= `nums[i]` <= 10^4^

### 解答
#### Python

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        data = nums[:k]
        heapq.heapify(data)
        for num in nums[k:]:
            heapq.heappushpop(data, num)
        return min(data)

> [name=Yen-Chi Chen][time=Mon, Aug 14, 2023]

#### TypeScript

- quick select

partition 函式會回傳一個 pivot，這個 pivot 左邊的元素都比 pivot 大，右邊的元素都比 pivot 小，不斷呼叫 partition 然後每次檢查 pivot 的位置是否為 k - 1，如果是的話就回傳 pivot 的值。

function partition(arr: number[], left: number, right: number) {
  const pivot = arr[right];
  while (left < right) {
    while (left < right && arr[left] >= pivot) {
      left++;
    }
    arr[right] = arr[left];
    while (left < right && arr[right] <= pivot) {
      right--;
    }
    arr[left] = arr[right];
  }
  arr[right] = pivot;
  return left;
}

function findKthLargest(nums: number[], k: number): number {
  let low = 0;
  let high = nums.length - 1;
  let pivot = partition(nums, low, high);

  while (pivot !== k - 1) {
    if (pivot > k - 1) {
      high = pivot - 1;
      pivot = partition(nums, low, high);
    } else {
      low = pivot + 1;
      pivot = partition(nums, low, high);
    }
  }

  return nums[pivot];
}

- counting sort

function findKthLargest(nums: number[], k: number): number {
  const n = nums.length;
  let max = nums[0];
  let min = nums[0];

  for (const num of nums) {
    if (num > max) {
      max = num;
    }
    if (num < min) {
      min = num;
    }
  }

  const size = max - min + 1;
  const buckets = new Array(size).fill(0);
  for (let i = 0; i < n; i++) {
    buckets[nums[i] - min]++;
  }

  let remain = k;
  for (let i = size - 1; i >= 0; i--) {
    remain -= buckets[i];
    if (remain <= 0) {
      return i + min;
    }
  }

  return -1;
}

> [name=Sheep][time=Mon, Aug 14, 2023]

#### C++

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> kthFinder;
        for (int num : nums) {
            kthFinder.push(num);
            while (kthFinder.size() > k) {
                kthFinder.pop();
            }
        }
        return kthFinder.top();
    }
};

> [name=Jerry Wu][time=14 Aug 2023]

### Reference

[回到題目列表](https://marsgoat.github.io/XNnote/coding/leetcodeEveryDay.html)