前言

決定變改變一下模式，因為有點太花時間了。以後如果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