[Q3:English] Kth largest element

Given an array of integers arr and an integer k find the kth largest element. (1 ≤ k ≤ length of arr)
For example, arr = [4,2,9,7,5,6,7,1,3], k = 4, output : 6.

---

My ans

 

 

[ Method 1]

# Logic

Remove max element in the arr for k-1 times and return max element.

 

# Code

 

# Complexity

T(n,k) : (k-1) * 2n + n = O(kn)

S(n) : O(1)

 

 

 

 

[Method 2]

# Logic

Use sorting

 

# Code

 

# Complexity

T(n,k) : O(nlogn) + O(1) = O(nlogn)

S(n) : O(1)

 

 

[Method 3]

# Logic

Use priority Queue w/ heap.

Remove root element and replace for k-1 times.

 

 

# Code

 

# Complexity

 

Time Complexity Calculation

T(n,k) : n + n + (k-1)*logn + logn = O(n+klogn) => if k close to n, T(n,k) ≒ O(nlogn)

S(n) : O(n)