🍇 215.数组中的第k个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
思路
基本思想
找到第k个最大的元素本身很简单，可以使用堆排序或者普通排序找到第k个最大的元素，示例代码如下：
1
2
3
4
5
6
7
8
| class Solution {
//最大堆可以解决的问题
//排序之后找到第四个元素即可，相同的元素也占一位
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length-k];
}
}
|
但是题目中规定了时间复杂度为O(n)，那么就不能使用排序，只能一次遍历解决问题
于是想到了改造经典的排序算法，这里选择改造快速排序，快速排序的每一趟都将一个元素归类到正确的位置上，如果某一次归类的元素刚好处于倒数第k个位置上，那么这个位置上的元素就是要找的，以此为基础进行改造
基础的快速排序代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public static void quickSort(int[] nums,int low,int high){
if(low<high){
int i=low,j=high;
int temp=nums[low];
//第一遍需要找到存放temp的合适位置
while(i<j){//这个循环控制i和j来回的移动，最终找到temp的位置
//这个循环控制从右边找到一个比temp小的元素放到前面
while(j>i&&nums[j]>=temp)
j--;
if(i<j){
nums[i]=nums[j];
i++;
}
//这个循环控制从左边找到一个比temp大的元素放到后面
while(i<j&&nums[i]<=temp)
i++;
if(i<j){
nums[j]=nums[i];
j--;
}
}
//循环结束说明找到了temp的位置
nums[i]=temp;
nums[j]=temp;
//进行下一轮递归，直到分割成单元素的小数组
quickSort(nums,low,i-1);
quickSort(nums,i+1,high);
}
}
|
每次都将小于当前标志位的元素放到标志位的前面，大于标志位的元素放到标志位的后面，等于标志位的暂不处理，我们可以将这些元素划分成三种：
- 等于标志位的
- 小于标志位的
- 大于标志位的
将这三种元素进行归类，然后判断倒数第k个元素应该出现在哪一个集合中，然后继续在这个集合中进行操作，当找到倒数第k个元素时，可以直接返回，核心代码如下，需要注意下标的变化：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| for(int num:arr){//将当前集合划分成三部分
if(num>temp)
big.add(num);
else if(num<temp)
small.add(num);
else
equal.add(num);
}
if(k<=big.size()){//倒数第k个元素在较大的集合中
return help(big,k);
}else if(k-big.size()-equal.size()>0){//倒数第k个元素在较小的集合中
return help(small,k-big.size()-equal.size());
}else//倒数第k个元素在相等的集合中
return temp;
|
注意到当倒数第k个元素在较大的集合中时，查找的下标没有变化，直接传输k，这是因为倒数第k个元素是从后面开始计算的，如果目标元素出现在较大的集合中，那么就不会影响下标的变化
当倒数第k个元素出现在较小的集合中时，说明此时这个目标元素跨跨越了较大的集合和相等的集合，在查找下标时需要跨越这两个集合的长度，也就是下标变为k-big.size()-equal.size()
如果目标元素出现在相等的集合中，说明找到了目标元素，直接返回
执行流程
- 改造快速排序的代码，从将小元素放到前面，大元素放到后面改造为小元素放到前面，大元素放到后面，相等的元素放到中间
- 判断当前倒数第k个元素会出现在哪个集合，从而计算出新下标，递归搜索
- 一旦找到这个目标元素直接返回
代码
根据以上分析，得出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
//最大堆可以解决的问题
//排序之后找到第四个元素即可，相同的元素也占一位
public int findKthLargest(int[] nums, int k) {
//将给定的数组转换成容器，才能进行add操作
List<Integer> arr=new ArrayList<>();
for(int num:nums){
arr.add(num);
}
return help(arr,k);
}
public int help(List<Integer> arr,int k){
Random r=new Random();
int temp=arr.get(r.nextInt(arr.size()));
List<Integer> big=new ArrayList<>();
List<Integer> small=new ArrayList<>();
List<Integer> equal=new ArrayList<>();
//将给定的集合进行划分，判断倒数第k个元素在哪，从而再进行划分
for(int num:arr){
if(num>temp)
big.add(num);
else if(num<temp)
small.add(num);
else
equal.add(num);
}
if(k<=big.size()){//目标元素在大元素集合中
return help(big,k);
}else if(k-big.size()-equal.size()>0){//目标元素在小元素集合中
return help(small,k-big.size()-equal.size());
}else
return temp;
}
}
|
总结
主要是将快速排序的代码进行改造，当找到倒数第k个元素时立马返回，为了操作更方便，将数组转换成了集合