双路快排-力扣215.数组中的第K个最大元素java
目录
双路快排–力扣215.数组中的第K个最大元素（java）
使用快速排序算法（实际上是快速选择算法）解决数组中的第K个最大元素问题，可以通过以下步骤实现：
方法思路
快速选择算法：基于快速排序的分区思想，每次选择一个基准元素将数组分为两部分，左边的元素小于等于基准，右边的元素大于基准。
//缩小搜索范围：根据基准元素的位置与目标位置（n - k）的比较，决定继续处理左半部分还是右半部分。
随机化基准：通过随机选择基准元素，避免最坏时间复杂度，提高算法效率。
解决代码
class Solution {
public void quickSort(int[] nums, int left, int right) {
// 终止条件
if (left >= right) {
return;
}
// 索引
int index = partition(nums, left, right);
quickSort(nums, left, index - 1);
quickSort(nums, index + 1, right);
}
public int partition(int[] nums, int left, int right) {
int randomIdx = (int) (((Math.random()) * (right - left + 1)) + left);
swap(nums, randomIdx, left);
int i = left + 1, j = right, pivot = nums[left];
while (i <= j) { // 注意有\U0001f7f0， 比如 1 2
// i找到第一个大于等于基准点的元素
while (i <= j && nums[i] < pivot) {
i++;
}
// j找到第一个小于等于基准点的元素
while (i <= j && nums[j] > pivot) {
j--;
}
if (i <= j) {
swap(nums, i, j);
i++;
j--;
}
}
swap(nums, j, left);
return j;
}
public void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
public int findKthLargest(int[] nums, int k) {
quickSort(nums, 0, nums.length - 1);
return nums[nums.length - k];
}
}