Programming
Leetcode-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.
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
<解題一> sort
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
Time complexity: O(n log n) Space complexity: O(1)
<解題二> heap
class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums == null || nums.length ==0) return 0;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int num : nums){
minHeap.offer(num);
if(minHeap.size()>k){
minHeap.poll();
}
}
return minHeap.peek();
}
}
Time complexity: O(n log n) Space complexity: O(1)
<解題三> quickselect
```JAVA
class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums == null || nums.length ==0) return 0;
int left = 0;
int right = nums.length - 1;
while(true){
int pos = position(nums, left, right);
if(pos + 1 == k){
return nums[pos];
} else if(pos + 1 > k){
right = pos - 1;
} else{
left = pos + 1;
}
}
}
private int position(int[] nums, int left, int right){
int pivot = nums[left];
int l = left + 1;
int r = right;
while(l <= r){
if(nums[l] < pivot && nums[r] > pivot){
swap(nums, l ,r);
l++;
r--;
}
if(nums[l] >= pivot) l++;
if(nums[r] <= pivot) r--;
}
swap(nums, left, r);
return r;
}
private void swap(int[] nums, int left, int right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
Time complexity: O(n) Space complexity: O(1)