## Algorithm

Problem Name: 215. Kth Largest Element in an Array

Given an integer array `nums` and an integer `k`, return the `kth` largest element in the array.

Note that it is the `kth` largest element in the sorted order, not the `kth` distinct element.

You must solve it in `O(n)` time complexity.

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 <= 105`
• `-104 <= nums[i] <= 104`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int comp(const void *a, const void *b) {
return *(int *)b - *(int *)a;
}
int msort(int *nums, int left, int right, int m) {
int i, j, k;
i = left;
j = right;
k = nums[i];
while (i  <  j) {
while (i < j && nums[j] <= k) {
j --;
}
if (i < j) {
nums[i] = nums[j];
i ++;
}
while (i  <  j && nums[i] >= k) {
i ++;
}
if (i < j) {
nums[j] = nums[i];
j --;
}
}
if (i > left) {
nums[i] = k;
}
if (i == m) return nums[i];
else if (i  <  m) return msort(nums, i + 1, right, m);
else return msort(nums, left, i - 1, m);
}
int findKthLargest(int* nums, int numsSize, int k) {
#if 0  // 6ms
qsort(nums, numsSize, sizeof(int), comp);
return nums[k - 1];
#else  // 13ms
return msort(nums, 0, numsSize - 1, k - 1);
#endif
}
``````
Copy The Code &

Input

cmd
nums = [3,2,1,5,6,4], k = 2

Output

cmd
5

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), greater < int>());
return nums[k - 1];
}
};
``````
Copy The Code &

Input

cmd
nums = [3,2,1,5,6,4], k = 2

Output

cmd
5

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int findKthLargest(int[] nums, int k) {
int[] counter = new int[20001];
for (int num : nums) {
counter[num + 10000]++;
}
for (int i = counter.length - 1; i >= 0; i--) {
if (counter[i]  <  k) {
k -= counter[i];
} else {
return i - 10000;
}
}
return -1;
}
}
``````
Copy The Code &

Input

cmd
nums = [3,2,3,1,2,4,5,5,6], k = 4

Output

cmd
4

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findKthLargest = function(nums, k) {
if (!nums || k > nums.length) return 0;

const larger = [];
const smaller = [];
const pivot = nums[parseInt(nums.length / 2)];
let pivotCount = 0;

for (let i = 0; i  <  nums.length; i++) {
const ele = nums[i];

if (ele > pivot) larger.push(ele);
else if (ele === pivot) pivotCount++;
else smaller.push(ele);
}

if (larger.length >= k) return findKthLargest(larger, k);
else if (k - larger.length - pivotCount  < = 0) return pivot;
else return findKthLargest(smaller, k - larger.length - pivotCount);
};
``````
Copy The Code &

Input

cmd
nums = [3,2,3,1,2,4,5,5,6], k = 4

Output

cmd
4

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findKthLargest(self, nums, k):
return heapq.nlargest(k, nums)[-1]
``````
Copy The Code &

Input

cmd
nums = [3,2,1,5,6,4], k = 2

Output

cmd
5

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0215_KthLargestElementInAnArray
{
public int FindKthLargest(int[] nums, int k)
{
Suffle(nums);
Quick3WaySort(nums, 0, nums.Length - 1, k);
return nums[k - 1];
}

private void Suffle(int[] nums)
{
var random = new Random();
int N = nums.Length;
int r, temp;
for (int i = 0; i  <  N; i++)
{
r = random.Next(i + 1);

temp = nums[r];
nums[r] = nums[i];
nums[i] = temp;
}
}

private void Swap(int[] nums, int i, int j)
{
var temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}

private void Quick3WaySort(int[] nums, int lo, int hi, int k)
{
if (lo >= hi) return;
if (lo >= k) return;
if (hi  <  k - 1) return;

int lt = hi, gt = lo, i = lo;
int pivot = nums[i];
while (i  < = lt)
{
if (nums[i] > pivot)
Swap(nums, gt++, i);
else if (nums[i] < pivot)
Swap(nums, lt--, i);
else
i++;
}

Quick3WaySort(nums, lo, gt - 1, k);
Quick3WaySort(nums, lt + 1, hi, k);
}
}
}
``````
Copy The Code &

Input

cmd
nums = [3,2,1,5,6,4], k = 2

Output

cmd
5