215. Kth Largest Element in an Array - python3

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

My Answer 1: Accepted (Runtime: 60 ms - 86.33% / Memory Usage: 14.9 MB - 61.73%)

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

nums 정렬 후 k 번째로 큰 값 반환하기

sort(): O(N Log N)

이거랑 비슷한 solution 을 올린 사람이 꽤 많았는데... 그 중 내 맘을 후벼판 답변이 있었다..

I think the best solution is to implement quickselect which will give you O(n).
This is a MEDIUM level problem, using the "built-in" sorting and picking an index is not right.

...난 양심이 없기 때문에 그냥 넘어가고 싶지만 quickselect 를 훑어는 봐주기로^^

Quick Select

Solution 1: Accepted (Runtime: 60 ms - 86.33% / Memory Usage: 15.3 MB - 14.56%)

from random import uniform


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        k = len(nums) - k
        # quick select
        def quick_select(nums: List[int], k: int) -> int:
            # base case
            if len(nums) <= 1:
                return nums[0]
            # choose a random pivot
            pivot = int(uniform(0, len(nums)))
            # split into left and right
            left, right = [], []
            for i, e in enumerate(nums):
                if i == pivot:
                    continue
                if e < nums[pivot]:
                    left.append(e)
                else:
                    right.append(e)
            # found it? we were lucky...
            if len(left) == k:
                return nums[pivot]
            # keep exploring
            if k < len(left):
                return quick_select(left, k)
            else:
                return quick_select(right, k - len(left) - 1)

        return quick_select(nums, k)

random 을 이용한 quick select

이거.. 알아서 짜라하면 못 짜요

Heap

Solution 2: Accepted (Runtime: 60 ms - 86.33% / Memory Usage: 15.2 MB - 17.80%)

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k, nums)[-1]

heap 이용

Solution 3: Accepted (Runtime: 68 ms - 47.11% / Memory Usage: 15.1 MB - 51.80%)

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for i in nums:
            if len(heap) < k:
                heapq.heappush(heap, i)
            elif i > heap[0]:
                heapq.heapreplace(heap, i)
        return heap[0]

minheap 이용
O(n*log(k)) 인거 보면 sort() 랑 비슷한듯