215. Kth Largest Element in an Array

문제 자체는 간단하다. k번째로 큰 수를 찾는 문제다.

sort()를 사용하면 바로 해결할 수 있지만, 이 문제에서 바라는 해답은 정렬을 사용하지 않고 해결해보는 것이다.

Solution

1. 문제에서 정의한 숫자의 범위 만큼 배열을 할당해 배열 안의 숫자의 개수를 저장한다.
2. 개수를 저장한 배열을 역순으로 순회하면서 k번째로 큰 수를 찾는다.

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        cnt = [0]*20001 # -10*4 ~ 10*4
        
        for num in nums: cnt[10000 + num] += 1 # 숫자 개수 세기

        for i in range(20000, -1, -1):
            if cnt[i] != 0: k -= cnt[i] # 해당 숫자의 개수 만큼 k 감소
            if k <= 0: return i - 10000 # 해당 순위의 수 반환

시간 복잡도

1. 숫자의 개수를 저장할 때의 시간 복잡도는 배열의 크기에 비례해서 O(n),
2. 역순으로 순회하는 과정에서는 최악의 경우 O(20000)으로

전체적인 시간 복잡도는 O(n)이다.