0215. Kth Largest Element in an Array
Last updated
Was this helpful?
Last updated
Was this helpful?
Was this helpful?
https://leetcode.com/problems/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.
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 <= 104
-104 <= nums[i] <= 104
Iterative version:
class Solution {
public int findKthLargest(int[] nums, int k) {
// Edge cases: invalid input.
k--; // Kth largest, index = k - 1 in sorted array.
int start = 0,
Recursive versioned:
// quick select: set pivot, opposite direction two pointers
class Solution {
public int findKthLargest(int[] nums, int k) {
// sort, nlogn
// partition, quick select
// pivot, left/right
// edge cases
if (nums.length < 1) return -1;
return quickSelect(nums, 0, nums.length-1, k);
}
private int quickSelect(int[] nums, int s, int e, int k) {
// exit
if (s == e) return nums[s];
// init
int l = s, r = e, pivot = nums[(s+e)/2];
// loop
while (l <= r) {
while(l<=r && nums[l] > pivot) l++; // cannot put '==' here, will pass then entire list, cause stackoverfloww
while (l <= r && nums[r] < pivot) r--;
if (l <= r) {
if (l < r) swap(nums, l, r);
l++;
r--;
}
}
// determine which part contains kth
if (s + k - 1 <= r) return quickSelect(nums, s, r, k);
if (s + k - 1 >= l) return quickSelect(nums, l, e, k-(l-s)); // be careful set new value for k by k-(l-s)
return nums[r+1]; // when there is value in the middle, right, kth, left
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
// Time: O(n)
O(NlogK)