Tìm N phần tử lớn nhất trong list Python

Cho list số nguyên, tìm N phần tử lớn nhất. Có nhiều cách với độ phức tạp khác nhau.

Cách 1: Sort rồi slice (Đơn giản, O(n log n))

def top_n_sort(lst, n):
    return sorted(lst, reverse=True)[:n]

print(top_n_sort([40, 5, 10, 20, 9], 2))  # [40, 20]

Cách 2: heapq.nlargest (Tối ưu O(n log k))

import heapq

def top_n_heap(lst, n):
    return heapq.nlargest(n, lst)

print(top_n_heap([40, 5, 10, 20, 9], 2))  # [40, 20]

Cách 3: Selection algorithm (O(n) trung bình)

import random

def quickselect(lst, k):
    """Trả về k phần tử lớn nhất (không sort)"""
    if k >= len(lst):
        return sorted(lst, reverse=True)
    pivot = random.choice(lst)
    larger = [x for x in lst if x > pivot]
    equal = [x for x in lst if x == pivot]
    smaller = [x for x in lst if x < pivot]
    if k <= len(larger):
        return quickselect(larger, k)
    elif k <= len(larger) + len(equal):
        return larger + equal[:k - len(larger)]
    else:
        return larger + equal + quickselect(smaller, k - len(larger) - len(equal))

print(quickselect([40, 5, 10, 20, 9], 2))  # [40, 20] (thứ tự có thể khác)

Cách 4: Thủ công (O(n×k) – như bài gốc)

def top_n_manual(lst, n):
    result = []
    lst_copy = lst[:]
    for _ in range(n):
        if not lst_copy: break
        max_val = max(lst_copy)
        result.append(max_val)
        lst_copy.remove(max_val)
    return result

print(top_n_manual([12, 61, 41, 85, 40, 13, 77, 65, 100], 4))
# [100, 85, 77, 65]

So sánh

Khuyên dùng

• heapq.nlargest(n, lst) cho hầu hết trường hợp.
• sorted(lst, reverse=True)[:n] nếu n lớn hoặc cần ổn định.