题目来源

• leetcode：215. 数组中的第K个最大元素

题目描述

题目解析

调用库函数

class Solution {
    
public:
    int findKthLargest(vector<int>& nums, int k) {
    
        std::sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

class Solution {
    
public:
    int findKthLargest(vector<int>& nums, int k) {
    
        return sort(nums.begin(), nums.end(), greater<int>()), nums[k - 1];
    }
};

快速排序

这道题真正要考察的应该是快速排序

class Solution {
    
    static void show(vector<int>& array, int curr, int pos, std::string dot, bool need = true){
    
        for(auto i : array){
    
            std::cout << i << "\t";
        }
        std::cout << "\n";
        if(need){
    
            int len = array.size();
            for (int j = 0; j < len; ++j) {
    
                if(j == curr){
    
                    std::cout << "^" << "\t";
                }else if(j ==  pos){
    
                    std::cout << dot << "\t";
                }else{
    
                    std::cout << " " << "\t";
                }
            }
            std::cout << "\n";
        }

    }

    // 5, 4, 6
    static std::tuple<int, int> helan_image(vector<int>& array, int start, int  end){
    
        int less = start - 1;  // 小于
        int more = end + 1;
        int pivot = array[start];  // 取第一个元素为基准元素
        int curr = start; // 当前正在遍历元素的下标


        while (curr <= end){
    

            if(array[curr] < pivot){
    
                 show(array, curr, less + 1, "|");
                std::swap( array[curr++], array[++less]);
                  show(array, curr, less, "|", false);
            }else if(array[curr] > pivot){
    
                show(array,  curr, more - 1, "!");
                std::swap( array[curr], array[--more]);
                show(array,  curr, more, "!", false);
            }else{
    
                show(array,  curr, curr , "^");
                ++curr;
                show(array,  curr, curr , "^", false);
            }
        }

        return std::make_tuple(less + 1, more - 1);
    }
    static std::tuple<int, int> helan(vector<int>& array, int start, int  end){
    
        int less = start - 1;  // 小于
        int more = end + 1;
        int pivot = array[start];  // 取第一个元素为基准元素
        int curr = start; // 当前正在遍历元素的下标


        while (curr < more){
    
            if(array[curr] < pivot){
    
                std::swap( array[curr++], array[++less]);
            }else if(array[curr] > pivot){
    
                std::swap( array[curr], array[--more]);
            }else{
    
                ++curr;
            }
        }

        return std::make_tuple(less + 1, more - 1);
    }

    void quickSort(vector<int>& array, int start, int  end){
    
        if(start >= end){
    
            return;
        }

        std::tuple<int, int> mids = helan(array, start, end);
        quickSort(array, start, std::get<0>(mids) - 1);
        quickSort(array, std::get<1>(mids) + 1 , end);
        
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
    
        quickSort(nums, 0, (int)nums.size() - 1);
        return nums[nums.size() - k];
    }
};

使用优先队列

class Solution {
    
  
public:
    int findKthLargest(vector<int>& nums, int k) {
    
        // 大根堆
        std::priority_queue<int> q(nums.begin(), nums.end());
        for (int i = 0; i < k - 1; ++i) {
    
            q.pop();
        }
        return q.top();
    }
};

class Solution {
    
public:
    int findKthLargest(vector<int>& nums, int k)  {
    
       // 维护一个小顶堆
        std::priority_queue<int, std::vector<int>, std::greater<int>> q;
        int len = nums.size();
        for (int i = 0; i < len; ++i) {
    
            q.push(nums[i]);
            if(q.size() > k){
    
                q.pop();
            }
        }
        return q.top();
    }
};

当然我们也可以换成 multiset 来做

有限队列本质上是一个堆排序

• 按输入创建一个大小为k的最小堆(vector a(k))
• 把数组的前k个数字插入堆中(带比较的插入)
• 遍历数组剩余数字，大小合适的就插入堆中(排序过程)
• 堆顶元素即为所求的第k大，前k大中的最小者

复杂度：

• 时间复杂度O(nlogk)，遍历n个元素，只给k个排序
  P.S.
• 求最大的k个，用最小堆——要插入堆中只需要比堆中最小元素大即可
• 求最小的k个，用最大堆——要比堆中最大的小才能插入