刷題日記(10) Kth Largest Element in an Array

Rachel Yeh
7 min readJan 3, 2021

--

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: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

— — — — — (第一種用類似quick sort的方法來解) — — — — —

來源:https://alrightchiu.github.io/SecondRound/comparison-sort-quick-sortkuai-su-pai-xu-fa.html

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本身。

以畫分三部分為目標,先不用管左邊和右邊裡面sort的順序

先劃分成大部分,再逐漸劃分成小部分去排序,反正一開始就是丟兩邊,大於pivot和小於pivot,然後越排越小部分(縮小範圍),也就是n + n/2 + n/4 + n/8 ….的由來

quick sort會每一個part都排,但是這題因為只要找第k個大的數,因此只要縮小部分排一部分即可

解題思路:

先過濾例外條件和設一個swap function,開始遞迴

把array像切蛋糕一樣,先分成兩部分(不用管這兩部分裡面的順序),之後再依照k值大於小於pivot去選擇左邊或右邊再繼續切下去

在切更細之前的停止條件是right和left的位置交錯(代表左右邊皆遍歷過一遍,已交換完)

繼續切成更小的subarray時就是兩種組合(start , right)或是(left, end), 然後繼續找k值

最後可能在sub array(左右邊) 裡面找到k,或是左右邊都沒有找到的情況下在partition function的最後回傳nums[k]代表pivot就是答案

(main function)

  1. 設定例外情況(當array等於null / array的長度是0 / k<1 /k>array的長)時回傳-1; (但其實題目有給note ”k is always valid, 1 ≤ k ≤ array’s length.”, )所以後面兩個條件應該是不用的
  2. 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]

Sign up to discover human stories that deepen your understanding of the world.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

--

--

Rachel Yeh
Rachel Yeh

Written by Rachel Yeh

Taiwan /Software Engineer / Cryptoer

No responses yet

Write a response