kth最大元素

本题是 Leecode的 215.Kth Largest Element in an Array

Description

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.

分析

本题,想到了2种可行方式:

  1. 用排序算法,对数组进行排序,然后返回地k-1个元素即可,既然是训练分治,这里可以使用归并排序的方式。
  2. 设计一个k大小的窗口,然后从数组上滑过,每个元素与这k个元素比较,根据大小做处理。类似于插入排序的方式。
    本题准备实现一下1方式

Solution

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
36
37
38
39
40
41
42
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {

vector<int> sortedNums = sort(nums, 0, nums.size()-1);
return sortedNums[k-1];
}

vector<int> sort(vector<int>& nums, int low, int high){

vector<int> mergeNums;

if(low == high){
mergeNums.push_back(nums[low]);
return mergeNums;
}

int middle = (low + high)/2;
vector<int> lnums = sort(nums, low, middle);
vector<int> hnums = sort(nums, middle+1, high);

int i=0, j=0;

while(i<lnums.size() && j<hnums.size()){
if(lnums[i] >= hnums[j]){
mergeNums.push_back(lnums[i++]);
} else {
mergeNums.push_back(hnums[j++]);
}
}

while(i<lnums.size()){
mergeNums.push_back(lnums[i++]);
}

while(j<hnums.size()){
mergeNums.push_back(hnums[j++]);
}

return mergeNums;
}
};

总结

上边2种做法,1中对所有的数组进行了排序,2中对k个元素进行了排序,不是直接去找Kth,应该能直接找子数组与kth之间的关系来直接分治。想了一种k分的方式,取最大,然后再取这k个值的最小,但是错误的;还有2分各取k应该,排序然后取第K,也是一种做法,但受K的影响,如果K > length/2,还需要作转换,衰减也并不明显。
暂时并未想到可行的直接分治的方法

google了一下结果,发现有用快排方式的,有用二分方式的,复杂度都是nlog(n)