Leetcode 215. Kth Largest Element in an Array with Python

Alpha, Orderly·2023년 1월 3일

leetcode

목록 보기

9/89

본 문서는 https://www.udemy.com/course/master-the-coding-interview-big-tech-faang-interviews/ 강의를 참조하여 작성되었습니다.

문제

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

You must solve it in O(n) time complexity.

정수 배열 nums와 정수 k가 주어진다. 배열에서 k번째로 큰 숫자를 리턴하시오.
k번째로 큰 숫자는 배열을 내림차순 정렬했을때 k번째에 있는 것을 의미한다.

예시

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

제한

1 <= k <= nums.length <= 10^5
10^4 <= nums[i] <= 10^4

풀이법

1. Python의 list 내장함수 사용하기

주어진 배열을 sort(Reversed=True) 를 이용하여 내림차순으로 정렬 한 뒤 k 번째 숫자를 리턴하는 것이다.

class Solution(object):
    def findKthLargest(self, nums: list, k):
        nums.sort(reverse=True)
        return nums[k-1]

내장 함수를 쓴 만큼 엄청나게 짧은 코드이다.

심지어 return nums.sort(reverse=True)[k-1] 와 같이 작성하면 1줄에 처리가 가능하다.

시간복잡도는 sort()함수의 시간복잡도인 O(nlogn)과 같은데, Leetcode에서는 분명 O(n)의 시간복잡도고 해결하라 하였으니 이렇게 해도 풀리긴 해서 신기했다.

2. Bucket Sort 사용

숫자의 범위를 보면 숫자가 전체적으로 -10000 과 10000 사이에 있다는것을 알수 있다.

숫자의 최대 크기가 작기 때문에 O(n)의 시간복잡도를 가지는 버킷 정렬을 이용한다면 좀 더 빠르게 할수 있지 않을까 했다.

class Solution(object):
    # 버킷 정렬
    def bucketSort(self, nums):
        for i in range(7):
            bucket = [[], [], [], [], [], [], [], [], [], []]
            for num in nums:
                bucket[(num // (10**i)) % 10].append(num)
            idx = 0
            for b in range(9, -1, -1):
                for c in bucket[b]:
                    nums[idx] = c
                    idx += 1
        return nums

    def findKthLargest(self, nums, k):
        np = [x + 100000 for x in nums]
        return self.bucketSort(np)[k-1] - 100000

다만 음수가 포함되어 있어 정렬 전에 전체에 큰 양수를 더해주는 과정을 거쳤다.

버킷 정렬은 음수가 포함될수 없기 때문이다.

예상과는 달리 1번 보다 100ms정도만 덜 걸렸다

아마 O(nLogn)과 O(n)은 별 차이가 없는 듯 하다.