본 문서는 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)은 별 차이가 없는 듯 하다.
3. Quick Select
퀵정렬을 이용해 이를 구할수도 있다.
본 방식은 퀵정렬의 성질을 이용하는데 아래 사진을 참고하길 바란다.
https://favtutor.com/blogs/quick-sort-cpp
위 경우 맨 오른쪽에 있는 값을 기준으로 하여 왼쪽은 자신보다 작고 오른쪽은 자신보다 크게 되도록 하는 위치를 찾게 해주는 것이다.
최 상단의 정렬 결과 13은 5번째 자리에 가게 된다.
이를 이용해 k번째로 작은 숫자를 찾을수 있다.
예를 들어 4번째로 작은 숫자가 필요 할시
먼저 맨 오른쪽의 pivot의 위치를 찾아주고, 만약 피봇의 위치가 4이다, 그러면 맨 마지막 값이 정렬되었을때 위치 또한 4번째, 즉 pivot의 값을 리턴해주면 된다.
만약 pivot의 위치보다 작은 쪽이 찾아야 할 위치라면 왼쪽 부분만 새로 pivot의 위치를 찾아주면 된다.
만약 오히려 큰 경우라면 반대가 될 것이다.
말하자면 이 방식은 수시로 임시 정렬하는 binary search와 같은 모양새를 띄게 된다.
시간복잡도는 O(nlogn)으로 생각보다 2번과 실행속도는 크게 차이 나지 않았다.
아래는 코드와 설명이다.
( 2024 / 11 / 27 )
복기
- 한번 Maxheap 으로 풀어봤다.
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
max_heap = []
for num in nums:
heappush(max_heap, -num)
for _ in range(k - 1):
heappop(max_heap)
return -heappop(max_heap)- 이 문제는 관점에 따라 easy냐 medium이냐로 갈릴듯..
