[Day 6] Leetcode 215. Kth Largest Element in an Array (C++)

前言

决定变改变一下模式，因为有点太花时间了。以後如果daily challenge是easy~medium、比较可以短时间内完成的再写这个挑战的题目，其他时候则按照我原本主题性刷题的方式来分享相关题目XD
今天想要分享的是这题：215. Kth Largest Element in an Array，也是属於top 100 liked的题目。

想法

解法一

这题乍看之下的第一个想法：sort完再给答案就好啦！秒杀XD

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end()); // 其实只写了这两行
        return nums[nums.size()-k]; // 其实只写了这两行
    }
};

可以是可以啦~也accept了没有超时 不过时间复杂度就是O(nlogn)罗！STL sort排序的时间复杂度大概是如此。
但其实我们根本不需要这麽麻烦(指花时间上的麻烦，写法倒是挺轻松的XD)。为什麽呢？sort会把vector内的全部元素都排好，但其实我们只care答案，一点都不在乎其他元素有没有排好。

解法二

你可以想想，如果我现在要求array中的最大值，是不是直接把暂时最大值设为第一个元素，然後遍历到底，有更大的元素出现就更新暂时最大值，最後就是答案了？这样只需要O(n)的时间复杂度！
那第k大的元素其实做法也差不多，只是我们要暂存的就变成需要k个值，然後呢，我们就一直更新这k个值为目前最大的k个值就好了。
那我们要怎麽存放这k个值呢？最简单的做法就是设一个vector或array，但这样你每次在更新的时候就需要比较k次!
另外一种方法就是用heap来存，heap是一个可以直接取得(O(1))一个heap里面最大/最小值的结构，它在维护/insert上的复杂度则是O(logk)，这样我们在比较的时候就变成先去看目前的值有没有>heap里面最小的值，有的话再花O(logk)的复杂度去insert这个值，把本来的最小值pop掉就行了！
还有一个小技巧就是我们要让k越小越好，所以如果一个array有10个我们要第9大的，我们可以反过来去求第2小的数XD 这样可以加速很多~
整个程序码如下：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // make sure we can maintain the smallest heap
        if(k<=nums.size()/2){

            // maintain size-k min heap
            priority_queue<int, vector<int>, greater<int>> pq1;
            for(int i=0; i<nums.size() ;++i){
                // if the heap is not full
                if(pq1.size()<k){
                    pq1.push(nums[i]);
                } else{
                    if(pq1.top()<nums[i]){
                        // remove the smallest one
                        pq1.pop();
                        // add the new one, remain the heap structure
                        pq1.push(nums[i]);
                    }
                }
            }
            return pq1.top();
        }
        // reserve the smallest ones
        else{
            // maintain size-k max heap
            priority_queue<int> pq2;
            for(int i=0; i<nums.size() ;++i){
                // if the heap is not full
                if(pq2.size()<nums.size()-k+1){
                    pq2.push(nums[i]);
                } else{
                    if(pq2.top()>nums[i]){
                        // remove the largest one
                        pq2.pop();
                        // add the new one, remain the heap structure
                        pq2.push(nums[i]);
                    }
                }
            }
            return pq2.top();
        }   
    }
};

这样的时间复杂度应该是O(nlogk)~且k一定<=n/2

结语

其实这题是可以在O(n)时间内来完成的！不过我本来要练习的是priority queue方法，後来去查才发现有更快的方法！是运用quick sort的方式，以後有空再补上吧XD