Как найти k-й по величине элемент?

LeetCode 215. Три подхода по эффективности. Оптимальные — min-heap размера k или quickselect.

# Min-heap размера k — O(n log k), для streaming
import heapq
def findKthLargest(arr, k):
    h = []
    for x in arr:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)
    return h[0]

# Quickselect — average O(n), worst O(n^2)
def findKthLargest(arr, k):
    k = len(arr) - k   # индекс k-го наименьшего
    def quickselect(lo, hi):
        pivot = arr[hi]
        i = lo
        for j in range(lo, hi):
            if arr[j] <= pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
        arr[i], arr[hi] = arr[hi], arr[i]
        if i == k:    return arr[i]
        elif i < k:   return quickselect(i + 1, hi)
        else:         return quickselect(lo, i - 1)
    return quickselect(0, len(arr) - 1)

Sort — O(n log n), самый простой (sorted(arr)[-k]). Quickselect — самый быстрый в среднем; heap — для online/streaming или малого k.