Comment on page

215.Kth-Largest-Element-in-an-Array

215. Kth Largest Element in an Array

题目地址

题目描述

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

代码

Approach #0 Sort

class Solution {
public int findKthLargest(int[] nums, int k) {
}
}

Approach #1 Heap

class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1, n2) -> n1 - n2);
for (int n: nums) {
heap.add(n);
if (heap.size() > k) {
heap.poll();
}
}
return heap.poll();
}
}

Approach #2 Quickselect

class Solution {
int[] nums;
public int findKthLargest(int[] nums, int k) {
this.nums = nums;
int size = nums.length;
return quickselect(0, size - 1, size - k);
}
private int quickselect(int left, int right, int k) {
if (left == right) return nums[left];
int index = left + (right - left) / 2;
index = partition(left, right, index);
if (k == index) {
return nums[k];
} else if (k < index) {
return quickselect(left, index - 1, k);
} else {
return quickselect(index + 1, right, k);
}
}
private int partition(int left, int right, int index) {
int pivot = nums[index];
// 1. move pivot to end
swap(index, right);
// 2. move all smaller elements to the left
int start = left;
for (int i = left; i <= right; i++) {
if (nums[i] < pivot) {
swap(start, i);
start++;
}
}
// 3. move pivot to its final place
swap(start, right);
return start;
}
private void swap(int a, int b) {
int tmp = nums[a];
nums[a] = nums[b];
nums[b] = tmp;
}
}