刷題日記（10） Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
— — — — — (第一種用類似quick sort的方法來解) — — — — —
Quick Sort是一種「把大問題分成小問題處理」的Divide and Conquer方法，原本的Quick Sort時間複雜度是N(logN), 把Array全部排完，但是此題只要找到第k大的數就好，因此不用整個排完。
平均時間複雜度近似於：n + n/2 + n/4 + n/8 …. =O(2n) =>常數省略變成O(n)
但最壞的時間複雜度為：O(n²) (因為運氣壞的話每次只能排一個，跟原本quick sort worst case 一樣) (n)(n-1)(n-2)….
空間複雜度為: O(1) 因為原地交換了，不用額外空間。
總之Quick Sort 的精華就是Partition，藉由Partition把Array 劃分成比pivot大，和比pivot小，以及第三種情況，等於pivot本身。
先劃分成大部分，再逐漸劃分成小部分去排序，反正一開始就是丟兩邊，大於pivot和小於pivot，然後越排越小部分（縮小範圍），也就是n + n/2 + n/4 + n/8 ….的由來
解題思路：
先過濾例外條件和設一個swap function，開始遞迴
把array像切蛋糕一樣，先分成兩部分（不用管這兩部分裡面的順序），之後再依照k值大於小於pivot去選擇左邊或右邊再繼續切下去
在切更細之前的停止條件是right和left的位置交錯（代表左右邊皆遍歷過一遍，已交換完）
繼續切成更小的subarray時就是兩種組合（start , right）或是（left, end）, 然後繼續找k值
最後可能在sub array（左右邊） 裡面找到k，或是左右邊都沒有找到的情況下在partition function的最後回傳nums[k]代表pivot就是答案
(main function)
- 設定例外情況（當array等於null / array的長度是0 / k<1 /k>array的長）時回傳-1; (但其實題目有給note ”k is always valid, 1 ≤ k ≤ array’s length.”, )所以後面兩個條件應該是不用的
- return Partition function，傳入array，最左邊index和最右邊index，還有要尋找的第k大的數（nums, 0, nums.length-1 , nums.length -k）這邊第k大的數用nums.length -k的關係是因為array的index從0開始
（Partition function）
3. 接收main function傳入的args為（nums, start, end, k）
4.當 start 大於等於 end 時，return nums[k]，表示array list長度為1。直接回傳答案
5. 拿變數left等於start , 再拿變數right等於end; (這邊都是指index)
6. 設定一下pivot，為array的中間值（ nums[ start + end]/2 ），注意這邊是值不是index
7. while (right大於等於left時)（就是right的位置要到left的左邊才會停下來）
7.1 while (right大於等於left 以及 陣列中的left所在位置的值小於pivot), left 往前走一步 (因為pivot的左邊一定小於他，就表示不用排)，直到找到值大於pivot或是right和left的位置已經交錯才停下來
7.2 while (right大於等於left 以及 陣列中的right所在位置的值大於pivot), right朝left走一步（right-1），同7.1必須找到不屬於右邊部分的（比pivot小或是right和left已經交錯才停下來）
7.3 如果（right大於left時），交換左右邊index所在位置的值，然後各往前走一步，(left +1) 以及（right-1），這裡的意思是說上面兩個while都幫right和left各找到不屬於左右邊的值，因此停下來交換(swap function)。 交換完之後繼續最外面的迴圈7的地方，繼續跑7.1 && 7.2 && 7.3 直到已經分成兩半 （此時的right和left已經等於或交錯，代表都遍歷過一遍了）
8. 當7的迴圈結束，我們可以知道粗略的排序下，該array被分成了大於pivot和小於pivot，因此可以知道k在pivot的左邊還是右邊
9.如果k小於right，因為上面7的迴圈結束，right此時應該在pivot的左邊，return Partition (nums, start, right, k) 意思是擷取pivot的左邊繼續遞迴。
10.如果k大於left ，因為上面7的迴圈結束，left此時應該在pivot的右邊，return Partition (nums, left, end, k) 意思是擷取pivot的右邊繼續遞迴。
11.最後當左右邊都找不到時直接return nums[k]代表pivot就是答案(遞迴出口)
(swap function)
12. 多一個變數tmp去接住nums[i]的值，把nums[j]的值給nums[i]，最後再把tmp值給nums[j]
