난이도 - Medium
Intuition
이 문제는 다양한 방법으로 풀 수 있다.
1) Sort
단순히 주어진 배열을 sorting하고 k번째 값을 찾는 방식이다. 직관적이지만 인터뷰에서는 더 나은 솔루션을 생각할 필요가 있다.
class Solution:
def findKthLargest(self, nums, k):
nums.sort(reverse=True)
return nums[k - 1]Time Complexity: O(nlogn) n개의 원소를 가진 배열을 sorting할때는 O(nlogn)이 걸림을 기억하자.
Space Complexity: O(logn) - Java, C++ or O(n) - Python(Timsort)
2) Min-Heap
Heap은 최소값이나 최대값을 찾는데 주로 쓰이는 유용한 자료구조이다.
Heap을 만들어서 num값을 확인하면서 Heap에 넣고, Heap사이즈가 k보다 커지면 heappop()을 하는식으로 k번째 큰 값을 가지고 있으면 된다. 그리고 마지막에 heappop()을 해주면 k번째 큰 값을 가질 수 있다.
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap)
return heapq.heappop(heap)Time Complexity: O(nlogk) Heap의 크기는 k개로 한정되므로, heappush()를 할 때 O(logk)만큼의 시간이 걸리게 된다. 이걸 n번 반복하므로 O(nlogk)가 나온다. k <= n이므로 O(nlogn)보다는 나은 성능을 보인다.
Space Complexity: O(k) Heap은 k개 만큼의 공간을 가진다.
3) Quickselect
Quickselect는 K번째로 작은 원소를 찾는데에 특화된 알고리즘이다. 이것이 효율적인 이유는 Average runtime 이 O(n)이기 때문이다.
우리는 K번째로 작은 원소가 아닌 큰 원소를 찾기 때문에 다르게 접근해야 한다. 따라서 알고리즘은 다음과 같다.
1. 랜덤하게 하나의 원소를 고른다. 이걸 mid라고 하겠다.
2. mid보다 큰 원소들은 left, 작은 원소들은 right에 모은다.
3. left 원소들의 개수가 K보다 크거나 같으면, 우리가 원하는 답은 무조건 left안에 있게 된다. 따라서 left를 가지고 위의 1,2단계를 다시 하면 된다.
4. left 원소들의 개수가 K보다 작으면, 답은 무조건 right에 있게 된다. 여기서는 K에서 left원소의 개수와 mid의 개수(1개)를 뺀 값을 다시 K로 설정해서 right에서 위의 1,2단계를 다시 하면 된다.
5. 만약에 left에도 right에도 답이 없다면, 정답은 mid이다.
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
def quick_select(nums, k):
pivot = random.choice(nums)
left, mid, right = [], [], []
for num in nums:
if num > pivot:
left.append(num)
elif num < pivot:
right.append(num)
else:
mid.append(num)
if len(left) >= k:
return quick_select(left, k)
elif len(left) + len(mid) < k:
return quick_select(right, k - len(left) - len(mid))
return pivot
return quick_select(nums, k)Time Complexity: O(n) - average, O(n^2) - worst case when choosing greatest or smallest element everytime. O(nlogn)이 아니냐 생각이 들 수도 있겠지만 master theorem with a=1,b=2,k=1을 사용하면 O(n)이 나온다.(https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms))
Space Complexity: O(n)
4) Counting Sort
Counting sort는 비교하지 않는 sorting 알고리즘이다. 이 알고리즘은 양의 정수들을 sorting하는데 유용하게 쓰인다.
알고리즘은 다음과 같이 작동한다.
1. array에서 가장 큰 값(maxVal)과 가장 작은 값(minVal)을 찾는다. 그리고 count라는 이름의 array를 만들고 사이즈는 maxVal-minVal+1로 세팅한다.
2. array를 돌면서 각 원소들의 frequency를 계산한다. 이건 count[num] += 1로 할 수 있다.
3. 이제 우리는 모든 원소들의 frequency를 알고 있다. count를 돌면서 해당되는 값을 k에서 뺀다. k가 0보다 작거나 같으면 거기에 해당되는 값이 우리가 찾고자 하는 K번째로 큰 값이다.
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
minVal = min(nums)
maxVal = max(nums)
count = [0] * (maxVal - minVal + 1)
for num in nums:
count[num-minVal] += 1
cur_k = k
for num in range(len(count)-1, -1, -1):
cur_k -= count[num]
if cur_k <= 0:
return num + minVal
return -1Time Complexity: O(n+m)
- maxVal과 minVal를 찾을때 각각 O(n)이 걸린다.
- count만드는데 O(m)
- count에 값 집어넣는데 O(n)
- count돌면서 K번째로 큰 값 찾는데 O(m)
Space Complexity: O(m) count가 m만큼 공간을 차지.