Chọn phần tử lớn thứ n từ List trong thời gian tuyến tính Python

Thuật toán Quickselect (chọn pivot, partition) tìm phần tử lớn thứ i (i=1 là lớn nhất) với độ phức tạp trung bình O(n).

Ví dụ

def select_largest(arr, left, right, i):
    if right - left <= 1:
        return arr[left]
    pivot_idx = partition(arr, left, right)
    k = right - pivot_idx  # số phần tử >= pivot
    if i < k:
        return select_largest(arr, pivot_idx + 1, right, i)
    elif i > k:
        return select_largest(arr, left, pivot_idx, i - k)
    return arr[pivot_idx]

def partition(arr, left, right):
    pivot = arr[left]
    i = left + 1
    j = right - 1
    while True:
        while i <= j and arr[i] <= pivot:
            i += 1
        while i <= j and arr[j] >= pivot:
            j -= 1
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
        else:
            arr[left], arr[j] = arr[j], arr[left]
            return j

arr = list(map(int, input("Nhập dãy số: ").split()))
i = int(input("Nhập i (1 là lớn nhất): "))
print("Kết quả:", select_largest(arr, 0, len(arr), i))

Kết quả

Nhập dãy số: 34 67 12 0 999
Nhập i (1 là lớn nhất): 1
Kết quả: 999

Giải thích

• Partition chia mảng thành 2 phần: <= pivot và >= pivot.
• K so với vị trí pivot để quyết định đệ quy bên nào.
• Trung bình O(n), tệ nhất O(n^2).