给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
提示：
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解一
排序 O(n*logn)
public int findKthLargest(int[] nums, int k) {
// 调用Arrays.sort()将数组从小到大排序
Arrays.sort(nums);
// 由于取第k个最大的数，所以是第n-(k-1)个最小的数
return nums[nums.length - k];
}题解二
仅对前k个数插入排序 O(n*k)
public int findKthLargest(int[] nums, int k) {
int[] sorted = new int[k];
int m = 0;
sorted[m] = nums[0];
for (int i = 1; i < nums.length; ++i) {
if (nums[i] > sorted[m]) {
if (m + 1 < k) {
m++;
}
int j = m;
for (; j > 0; --j) {
if (nums[i] <= sorted[j - 1]) {
break;
}
sorted[j] = sorted[j - 1];
}
sorted[j] = nums[i];
} else if (m < k - 1) {
sorted[++m] = nums[i];
}
}
return sorted[k - 1];
} public int findKthLargest(int[] nums, int k) {
for (int i = 1; i < nums.length; i++) {
int tmp = nums[i];
if (i < k || tmp > nums[k-1]) {
int j = Math.min(i, k - 1);
while (j > 0 && tmp > nums[j - 1]) {
nums[j] = nums[j - 1];
j--;
}
if (j != i) {
nums[j] = tmp;
}
}
}
return nums[k - 1];
}题解三
仅对前k个数排序 O(n*k*logk)
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums, 0, k);
for (int i = k; i < nums.length; ++i) {
if (nums[i] > nums[0]) {
nums[0] = nums[i];
Arrays.sort(nums, 0, k);
}
}
return nums[0];
}题解四
堆排序
使用Java的优先队列排序。
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int n : nums) {
queue.add(n);
if (queue.size() > k) {
queue.poll();
}
}
return queue.poll();
}public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;
build(nums, heapSize);
for (int i = nums.length - 1; i > nums.length - k; --i) {
swap(nums, 0, i);
heapSize--;
heapify(nums, 0, heapSize);
}
return nums[0];
}
private void build(int[] arr, int heapSize) {
for (int i = heapSize / 2; i >= 0; --i) {
heapify(arr, i, heapSize);
}
}
private void heapify(int[] arr, int index, int heapSize) {
int left = index << 1;
int right = left + 1;
int large = index;
if (left < heapSize && arr[left] > arr[large]) {
large = left;
}
if (right < heapSize && arr[right] > arr[large]) {
large = right;
}
if (arr[large] > arr[index]) {
swap(arr, index, large);
heapify(arr, large, heapSize);
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}题解五
二分，利用快速排序的思想。
/**
* 返回数组第k个最大的数。
*
* @param nums 目标数组
* @param k 第k个最大的数
* @return 返回数组第k个最大的数
*/
public int findKthLargest(int[] nums, int k) {
// 从0到n-1区间寻找第k个最大的数，下标-1
return quickSelect(nums, 0, nums.length - 1, k - 1);
}
/**
* 在数组区间上寻找第k大的数。
*
* @param arr 目标数组
* @param left 数组的左边界
* @param right 数组的右边界
* @param target 待寻找的第k大数下标
* @return 返回第k大数的值
*/
private int quickSelect(int[] arr, int left, int right, int target) {
// 分区，得到基准元素坐标
int q = partition(arr, left, right);
if (q == target) { // 基准元素坐标是目标坐标
// 返回目标值
return arr[q];
}
if (q < target) { // 基准元素坐标在目标坐标右边
// 继续在右边区间寻找
// ...left...... q ...target....right...
// ...| <=pivot |pivot| >=pivot |...
// |------------|
return quickSelect(arr, q + 1, right, target);
} else { // 基准元素坐标在目标坐标左边
// 继续在左边区间寻找
// ...left..target.. q ..........right...
// ...| <=pivot |pivot| >=pivot |...
// |------------|
return quickSelect(arr, left, q - 1, target);
}
}
/**
* 将数组分区为3部分：[<=pivot][pivot][>=pivot]。返回pivot的坐标。
*
* @param arr 待分区的数组
* @param left 分区的左边界
* @param right 分区的右边界
* @return 返回分区中间pivot的坐标
*/
private int partition(int[] arr, int left, int right) {
// 在[left, right]区间随机取一个数当做基准
int q = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
int pivot = arr[q];
// 将基准数交换到区间最右边：[...]pivot
swap(arr, q, right);
// >=区间的右边界
// |>=区间|待处理区间|pivot|
// |left.....right|
int i = left - 1;
// 从区间最左边元素到最右边-1元素
for (int j = left; j < right; ++j) {
// 如果当前数比基准数大
if (arr[j] > pivot) {
// 交换当前元素到>=区间的右边界
// |>=区间|<=区间|待处理区间|pivot|
// |....i|X.....|j.......|pivot|
// |......j|.....X|......|pivot|
swap(arr, ++i, j);
}
}
// 将基准元素交换回>=区间的右边界+1
swap(arr, i + 1, right);
// 返回>=区间的右边界+1，即基准元素坐标
return i + 1;
}
/**
* 交换数组两个元素的值。
*
* @param arr 需要交换的数组
* @param i 需要交换的元素下标1
* @param j 需要交换的元素下标2
*/
private void swap(int[] arr, int i, int j) {
if (i == j) return;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
