Kth Largest Element in an Array

Q: Độ phức tạp thời gian của bài toán tìm phần tử lớn thứ K trong mảng là bao nhiêu?

Việc sắp xếp mất thời gian O(n log n) . Một đống tối thiểu có kích thước k mất thời gian O(n log k) và cần O(k) bộ nhớ. Quickselect với chốt ngẫu nhiên mất thời gian O(n) trung bình và O(n²) trong trường hợp xấu nhất, nhưng chốt ngẫu nhiên khiến trường hợp này rất khó xảy ra.

Q: Tôi nên dùng heap hay quickselect để tìm phần tử lớn thứ k?

Quickselect có tốc độ trung bình nhanh hơn, O(n) , nhưng cần lưu tất cả giá trị trong bộ nhớ và sắp xếp lại chúng. Heap có độ phức tạp O(n log k) , không có trường hợp xấu nhất quá tệ và hoạt động tốt khi các giá trị lần lượt được đưa vào.

Trung bìnhHeap Sắp xếp

+10

Bạn nhận được một mảng số nguyên nums và một số nguyên k. Hãy trả về giá trị lớn thứ k trong nums: giá trị ở vị trí k, tính từ 1, sau khi sắp xếp mảng theo thứ tự giảm dần.

Các giá trị bằng nhau được tính riêng. Trong [5, 5, 1], giá trị lớn nhất là 5 và giá trị lớn thứ hai cũng là 5.

Hàm

findKthLargest(nums: integer-array, k: integer) → integer

numsinteger-array: các giá trị cần xếp hạng
kinteger: nên trả về giá trị lớn nhất nào, 1 cho giá trị lớn nhất
Trả vềinteger: giá trị lớn thứ k, tính cả các giá trị trùng lặp

Ràng buộc

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Các giá trị bằng nhau vẫn được tính là các giá trị riêng biệt.

Ví dụ

Đầu vào: nums = [7, 2, 9, 4, 9, 1]k = 2
Đầu ra: 9
Giải thích: Theo thứ tự từ lớn nhất đến nhỏ nhất, các giá trị là 9, 9, 7, 4, 2, 1. Hai số 9 được tính riêng, nên số lớn thứ hai là 9, không phải 7.

Đầu vào: nums = [5, -3, 8, 0, 2]k = 4
Đầu ra: 0
Giải thích: Sắp xếp các giá trị từ lớn nhất đến nhỏ nhất, ta có 8, 5, 2, 0, -3, và giá trị thứ tư là 0.

Đầu vào: nums = [6]k = 1
Đầu ra: 6
Giải thích: Với một giá trị và k = 1, giá trị đó là lớn nhất.

Câu hỏi mở rộng

Các giá trị giờ đến lần lượt từng giá trị một. Sau mỗi lần có giá trị mới, bạn có thể báo cáo trung vị của tất cả giá trị đã thấy cho đến lúc đó trong thời gian O(log n) cho mỗi giá trị không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Bạn chỉ cần một vị trí trong thứ tự đã sắp xếp, không cần tất cả n. Min-heap có kích thước k chỉ giữ lại các giá trị vẫn có thể là đáp án, còn quickselect phân vùng như quicksort nhưng chỉ đi theo phía chứa đáp án, nhờ đó giảm thời gian trung bình xuống còn O(n).

Sắp xếp và đọc một vị trí

Ý tưởng

Giá trị lớn thứ k được xác định theo thứ tự đã sắp xếp, vì vậy hãy sắp xếp rồi đọc một vị trí: chỉ số k-1 khi sắp xếp từ lớn đến nhỏ, hoặc chỉ số n-k khi sắp xếp từ nhỏ đến lớn. Khi sắp xếp từ lớn đến nhỏ, ví dụ đầu tiên là [9, 9, 7, 4, 2, 1], và chỉ số 1 chứa số 9 thứ hai. Mỗi bản sao của một giá trị vẫn giữ vị trí riêng.

Với n = 10^4, việc sắp xếp thực hiện khoảng 1.3 × 10^5 phép so sánh, sắp xếp toàn bộ n giá trị trong khi chỉ một vị trí là quan trọng.

Thuật toán

Sao chép nums để mảng của bên gọi giữ nguyên như ban đầu.
Sắp xếp bản sao. Dùng phép so sánh số, vì một số ngôn ngữ mặc định so sánh số như văn bản.
Trả về chỉ số k-1 trong thứ tự từ lớn đến nhỏ, hoặc chỉ số n-k trong thứ tự từ nhỏ đến lớn.

def findKthLargest(nums, k):
    # Largest first: the k-th largest sits at index k-1.
    ordered = sorted(nums, reverse=True)
    return ordered[k - 1]

Giữ lại k phần tử lớn nhất trong min-heap

Ý tưởng

Giá trị lớn thứ k là giá trị nhỏ nhất trong k giá trị lớn nhất. Vì vậy, hãy duyệt qua nums một lần và giữ lại k giá trị lớn nhất đã gặp trong một đống tối thiểu, với phần tử đầu đống là giá trị nhỏ nhất.

Khi đống có đủ k giá trị, hãy so sánh từng x mới với phần tử đầu đống. Nếu x không lớn hơn, thì k giá trị được giữ lại đều lớn hơn hoặc bằng nó, nên x không thể là đáp án. Nếu lớn hơn, phần tử đầu đống bị loại khỏi k giá trị lớn nhất và x thay thế nó. Trong ví dụ 2 với k = 4, phần tử đầu đống sau bốn giá trị đầu tiên là -3; 2 thay thế nó, và phần tử đầu đống mới, 0, là đáp án.

Mỗi giá trị cần nhiều nhất một bước xử lý đống với độ phức tạp O(log k): thời gian O(n log k) và bộ nhớ O(k).

Thuật toán

Bắt đầu với một min-heap rỗng.
Với mỗi giá trị x, thêm nó vào khi đống còn ít hơn k giá trị.
Khi đống đã có k giá trị, chỉ thay phần tử trên cùng bằng x nếu x lớn hơn phần tử trên cùng.
Sau giá trị cuối cùng, trả về phần tử trên cùng của đống.

import heapq


def findKthLargest(nums, k):
    # A min-heap of the k largest values so far; its top is the smallest of them.
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x
    return heap[0]

Quickselect với phân hoạch ba chiều

Ý tưởng

Sau một lần phân hoạch nhanh, chốt nằm ở chỉ số cuối cùng trong thứ tự đã sắp xếp, dù hai phía vẫn chưa được sắp xếp. Theo thứ tự từ nhỏ đến lớn, đáp án nằm tại target = n-k, vì vậy sau mỗi lần phân hoạch, bạn chỉ tiếp tục ở phía chứa target.

Trong ví dụ đầu tiên, target là 4. Phân hoạch quanh 4 đặt 7, 9, 9 ở các chỉ số từ 3 đến 5, nên bạn giữ lại phía đó. Phân hoạch phía đó quanh 9 đặt cả hai số 9 ở các chỉ số 4 và 5, và chỉ số 4 chứa đáp án.

Phân hoạch ba chiều nhóm các giá trị bằng chốt vào [lt, gt], ở đúng vị trí đã sắp xếp, nên nếu target nằm trong đó thì tìm kiếm kết thúc. Một chốt ngẫu nhiên rơi vào nửa giữa trong một nửa số lần, thu hẹp phạm vi xuống tối đa còn ba phần tư, nên khối lượng công việc kỳ vọng là O(n); trường hợp xấu nhất vẫn là O(n²). Phân hoạch một bản sao tốn O(n) bộ nhớ.

Thuật toán

Sao chép nums vào a, đặt target = n-k, lo = 0 và hi = n-1.
Chọn một chốt ngẫu nhiên từ a[lo..hi].
Phân hoạch a[lo..hi] thành các giá trị nhỏ hơn, bằng và lớn hơn chốt, giữ các giá trị bằng chốt trong a[lt..gt].
Nếu target < lt, đặt hi = lt-1; nếu target > gt, đặt lo = gt+1; nếu không, trả về chốt.
Lặp lại từ bước 2.

import random


def findKthLargest(nums, k):
    a = list(nums)
    target = len(a) - k  # the answer's index once a is sorted smallest first
    lo, hi = 0, len(a) - 1
    while True:
        pivot = a[random.randint(lo, hi)]
        # Three-way partition of a[lo..hi]: < pivot, then == pivot, then > pivot.
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
            else:
                i += 1
        # Now a[lt..gt] all equal pivot, and they are in their sorted places.
        if target < lt:
            hi = lt - 1
        elif target > gt:
            lo = gt + 1
        else:
            return pivot

Lỗi thường gặp và trường hợp biên

Xóa phần tử trùng lặp trước. Trong ví dụ đầu tiên, đáp án là 9, nhưng sau khi chuyển mảng thành tập hợp, đáp án trở thành 7.
Đọc chỉ số n-k-1. k đếm từ 1, nên đáp án nằm ở vị trí n-k khi sắp xếp theo thứ tự tăng dần.
Sắp xếp số dưới dạng văn bản. Trong JavaScript và TypeScript, [10, 9, 2].sort() cho kết quả [10, 2, 9]; hãy truyền (a, b) => a - b.
Dùng max-heap có kích thước k. Loại bỏ giá trị lớn nhất sẽ giữ lại k giá trị nhỏ nhất và trả về giá trị nhỏ thứ k.
Dùng Quickselect với cách phân hoạch hai chiều hoặc một pivot cố định. 10^4 bản sao của 7, hoặc một mảng đã sắp xếp, khiến phạm vi thu hẹp một giá trị sau mỗi vòng: khoảng 5 × 10^7 bước.

Câu hỏi thường gặp4

Độ phức tạp thời gian của bài toán tìm phần tử lớn thứ K trong mảng là bao nhiêu?

Việc sắp xếp mất thời gian O(n log n). Một đống tối thiểu có kích thước k mất thời gian O(n log k) và cần O(k) bộ nhớ. Quickselect với chốt ngẫu nhiên mất thời gian O(n) trung bình và O(n²) trong trường hợp xấu nhất, nhưng chốt ngẫu nhiên khiến trường hợp này rất khó xảy ra.

Tại sao dùng min-heap thay vì max-heap để tìm phần tử lớn thứ k?

Giá trị bạn đem ra so sánh rồi loại bỏ là giá trị nhỏ nhất trong số k giá trị lớn nhất, nên nó phải nằm trên cùng. Heap tối đa chỉ hoạt động nếu bạn đưa cả n giá trị vào heap rồi lấy ra k-1 lần, cách này cần bộ nhớ O(n).

Tôi nên dùng heap hay quickselect để tìm phần tử lớn thứ k?

Quickselect có tốc độ trung bình nhanh hơn, O(n), nhưng cần lưu tất cả giá trị trong bộ nhớ và sắp xếp lại chúng. Heap có độ phức tạp O(n log k), không có trường hợp xấu nhất quá tệ và hoạt động tốt khi các giá trị lần lượt được đưa vào.

Có thể tìm phần tử lớn thứ k trong thời gian tuyến tính ở trường hợp xấu nhất không?

Có. Quy tắc median-of-medians chọn một pivot, bảo đảm loại bỏ một tỷ lệ cố định các giá trị, nhờ đó việc chọn phần tử có độ phức tạp O(n) trong trường hợp xấu nhất, dù chậm hơn trong thực tế. Với các giá trị từ -10^4 đến 10^4, đếm từng giá trị cũng có thể chạy trong thời gian tuyến tính.

def findKthLargest(nums, k):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [7, 2, 9, 4, 9, 1]
k = 2

Đầu ra mong đợi

Kth Largest Element in an Array

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Sắp xếp và đọc một vị trí

Giữ lại k phần tử lớn nhất trong min-heap

Quickselect với phân hoạch ba chiều

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp4

Bài tập tương tự