215. Kth Largest Element in an Array

找第K個大的數

1. 排序完再解
2. 開一個Priority_queue(每次pop都從最小的開始) PS:Priority_queue如何做到的? Heap與 Dijkstra’s algorithm 一起實作

int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> PQ;
        
        for(int i=0; i<nums.size(); i++)
        {
            PQ.push(nums[i]);
            if(PQ.size() > k) PQ.pop();
        }
        
        return PQ.top();
        
    }

3.借用QuickSort的概念，每次做完一輪partion之後看pivot的index是不是我們要的。不是的話就往靠近的那邊繼續找 Worst Case(n²)

class Solution {
public:
    int partition(vector<int>& nums, int l,int r){
        int temp = nums[l];
        while(l < r){
            int temp = nums[l];
            while(l < r){ 
              //這邊的排法是在右邊找到比較大的 換到左邊
                while(l < r && nums[r] <= temp) r--;
                swap(nums[l],nums[r]);
             //下面相反是找到左邊開始找找到小的換到右邊
                while(l < r && nums[l] >= temp) l++;
                swap(nums[l],nums[r]);
            } //反正被換的其中一個數字一定是 pivot值
        }
        nums[l] = temp;
        return l;
    }
    int search(vector<int>& nums,int l,int r,int k){
        int m =partition(nums,l,r);//大排到小
        if(m == k-1) return nums[m];
        //找到的太小往左邊找
        else if(m > k-1) return search(nums,l,m-1,k);
        else return search(nums,m+1,r,k);
    }
    int findKthLargest(vector<int>& nums, int k) {
        int length = nums.size();
        if(k > length) return 0;
        else return search(nums,0,length-1,k);
    }
};

我覺得這邊比較重要的是要了解quickSort的方法，以下是另外一種寫法

int partition(int arr[], int l, int r){//最左index 跟 最右邊
  int x = arr[r], i = l;
  for (int j = l; j <= r ; j++) {
     if (arr[j] <= x) { //這是小排到大
       swap(&arr[i], &arr[j]);
       i++;
     }
  }
  swap(&arr[i], &arr[r]);
  return i;
}

總之如果是要問第幾個大的就是大排到小

反過來如果是要問第幾個小的就是小排到大