題目來源

題目說明

解題思路

因爲只是要找第K大的元素，因此沒必要也盡量避免使用Sorting -- 而且因爲數據量較大，可能會超時

1. 建Min Heap
   核心概念：保持一個「大小為 k」的小堆，堆頂是目前第k大的元素

2. priority_queue (其實就是Max Heap)
   參考程式碼：

   class Solution {
   public:
    int findKthLargest(vector<int>& nums, int k) {
        int val = 0;
        priority_queue<int> pq;
        for(auto& e: nums){
            pq.push(e);
        }
        int i = 1;
        while(i < k){
            pq.pop();
            ++i;
        }
        val = pq.top();
        return val;
    }
   };

3. Quick_Select
   Quick_Select 快速選擇的思路是，因爲要找的是第k大，換句話說就是要找第n-k小的數(其中n是數組中的元素個數)。
   因此我們需要使用到快速排序的思路，最後只要找到索引是n-k的數就是答案。這裡要說明一下，因爲數組下標是從0開始，而現實生活中一般是從1開始計算起，因此會有一個數值差！
   參考程式碼：

   class Solution {
   public:
    int Partition(vector<int>& nums, int left, int right) {
        int RAND_IDX = left + rand() % (right - left + 1); // 這裡要注意使用rand()，如果不使用依然會超時
        int RAND_VAL = nums[RAND_IDX];
        swap(nums[RAND_IDX],nums[right]); // 將隨機到的pivot移到最後面
        // 下面在做的事情主要都是為了讓比RAND_VAL小的數在RAND_VAL的左邊
        int store_idx = left;
        for(int i = left;i<right;++i){
            if(nums[i] < RAND_VAL){
                swap(nums[store_idx++],nums[i]);
            }
        }
        swap(nums[store_idx],nums[right]);
        return store_idx;
    }
    int Quick_Select(vector<int>&nums,int left,int right,int k_smallest){
        if(left == right) return nums[left];
        int pivot_idx = Partition(nums,left,right);
        if(pivot_idx == k_smallest) return nums[pivot_idx]; // pivot_dx就是我們要找的
        else if(pivot_idx < k_smallest){ // pivot_idx < k_smallest -> 去右邊找
            return Quick_Select(nums,pivot_idx+1,right,k_smallest);
        }
        else{
            return Quick_Select(nums,left,pivot_idx-1,k_smallest);
        }
   
    }
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return Quick_Select(nums,0,n-1,n-k);
    }
   };

效率分析

1. Min Heap：時間O(nlogk) 空間O(1)
2. Priority_queue：和Min Heap一樣
3. Quick_Select：時間O(nlogn) worst：O(n^2) -- 因此才使用隨機 空間O(1)