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
}
Input
Output
#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];
}
};
Input
Output
#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;
}
}
Input
Output
#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);
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findKthLargest(self, nums, k):
return heapq.nlargest(k, nums)[-1]
Input
Output
#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);
}
}
}
Input
Output