leetcode-215-数组中第k个最大元素

发表于 | 分类于 | 本页总阅读量 次

可用三种方法：

第一种暴力法，先排序再取值，快速排序O(nlogn)

第二种固定k个元素的最小堆，遍历建堆完毕后取堆顶，建堆时间复杂度O(logk)，遍历数组中元素对堆进行调整工作是O(nlogk)。

第三种快速排序思想进行选择，分治后只递归一边，O(n)。

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
43
44
45
46
47
48
49
50
51
52
53
54
// 纯手写最小堆
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.size()<k||k==0){
            return -1;
        }
        // 最小堆
        vector<int> heap;
        int hsize=0;
        int i=0;
        for(i;i<nums.size();i++){
            // 堆满且堆顶最小值小于nums[i]
            if(hsize==k&&heap[0]<nums[i]){
                heap[0]=nums[i];
                adjustDown(heap,0,hsize);
            }
            // 堆还没满
            if(hsize<k){
                heap.push_back(nums[i]);
                adjustUp(heap,hsize);
                hsize++;             
            }
        }
        return heap[0];
        
    }
    // 堆的上浮操作，可用于依次添加元素
    void adjustUp(vector<int>& heap,int node){
        int p_index=(node-1)/2;
        while(node!=0){
            if(heap[node]<heap[p_index]){
                swap(heap[node],heap[p_index]);
            }
            node=p_index;
            p_index=(node-1)/2;
        }
    }
    // 堆的向下调整，可用于删除元素
    void adjustDown(vector<int>& heap,int node,int heap_cap){
        int child=node*2+1;
        while(child<heap_cap){
            if(child+1<heap_cap&&heap[child+1]<heap[child]){
                child=child+1;
            }
            if(heap[child]>=heap[node]){
                break;
            }  
            swap(heap[child],heap[node]);
            node=child;
            child=2*node+1;
        }
    }
};