215. Kth Largest Element in an Array

215. Kth Largest Element in an Array

 

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.

Can you solve it without sorting?

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

 

정렬 하는 방법

def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[-k]

 

힙으로..

def findKthLargest(self, nums: List[int], k: int) -> int:
	"""
    # - 붙임으로써 큰->작은순으로 정렬
    """
    heap = [] 
    for num in nums: 
        heapq.heappush(heap,-num) 
    while k > 0: 
        res = heapq.heappop(heap) 
        k -=1 
    return -res

 

퀵 정렬 사용

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        """
        무작위 피벗 선택: 
        - random.randint(l, r)로 무작위 인덱스를 피벗으로 선택하여 불균형한 분할을 방지합니다.

        피벗보다 작은 마지막 인덱스 추적 (lessEnd): 
        - 피벗보다 작은 요소의 마지막 위치를 lessEnd로 저장하여 
        - 중복된 피벗 값을 여러 번 처리하지 않도록 합니다.

        분할 조건:
        - k > p이면 오른쪽 부분을 탐색합니다.
        - k > lessEnd이면 nums[p]가 k번째 요소이므로 바로 반환합니다.
        - k <= lessEnd이면 왼쪽 부분을 탐색합니다.
        - 이렇게 하면 피벗의 중복을 반복적으로 처리하지 않으면서 최
        - 적화된 탐색을 수행할 수 있습니다.
        """
        n = len(nums)
        k = n - k  # k번째로 큰 요소는 오름차순으로 정렬 시 (n-k)번째 요소와 동일합니다.

        def quickSelect(l, r):
            pivotIndex = random.randint(l, r)  # 무작위로 피벗 인덱스 선택
            nums[pivotIndex], nums[r] = nums[r], nums[pivotIndex]  # 피벗을 맨 오른쪽으로 이동
            pivot = nums[r]  # 피벗 값 설정

            p = l  # 피벗보다 작거나 같은 요소의 위치를 추적할 포인터
            lessEnd = -1  # 피벗보다 작은 마지막 인덱스

            for i in range(l, r):
                num = nums[i]
                if num < pivot: # 피벗보다 작은 마지막 인덱스 업데이트
                    lessEnd = p  
                if num <= pivot: # 피벗보다 작거나 같은 요소를 왼쪽으로 이동
                    nums[p], nums[i] = nums[i], nums[p]  
                    p += 1

            nums[p], nums[r] = nums[r], nums[p]  # 피벗을 최종 위치로 이동

            # k가 현재 위치 p보다 크다면 오른쪽 부분 탐색
            if k > p:
                return quickSelect(p + 1, r)
            # k가 lessEnd보다 크고 p와 같다면 피벗 값 반환
            elif k > lessEnd:
                return nums[p]
            # k가 lessEnd보다 작으면 왼쪽 부분 탐색
            else:
                return quickSelect(l, lessEnd)

        return quickSelect(0, n - 1)

 

SortedList 사용

from sortedcontainers import SortedList

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        """
        자동 정렬:
            값이 삽입되거나 삭제될 때 자동으로 정렬됩니다.
            O(log n) 시간 복잡도로 정렬을 유지합니다.
        효율적인 인덱싱:
            리스트처럼 인덱스를 통해 값에 접근할 수 있습니다.
            O(log n) 시간 복잡도로 인덱싱 가능합니다.
        """
        res = SortedList()
        for n in nums:
            res.add(n)

        return res[-k]