Kth Largest Element in a Stream

Q: Tại sao dùng đống nhỏ nhất thay vì đống lớn nhất để tìm phần tử lớn thứ k?

Giá trị nhỏ nhất trong số k giá trị lớn nhất vừa là đáp án, vừa là giá trị mà một phần tử mới phải vượt qua, và một đống tối thiểu có kích thước k sẽ giữ giá trị đó ở trên cùng. Một đống tối đa chứa mọi giá trị sẽ đưa giá trị lớn nhất lên trên cùng, nên để đến giá trị thứ k , bạn phải lấy ra k-1 giá trị rồi đưa chúng trở lại mỗi khi có phần tử mới.

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

Mỗi lần phần tử đến có chi phí O(log k) : một lần so sánh với phần tử trên cùng và nhiều nhất một lần sàng qua một đống gồm k giá trị. Việc tạo đống từ nums có chi phí O(n log k) , vì vậy toàn bộ quá trình chạy mất O((n + m) log k) thời gian và cần thêm O(k) không gian.

DễHeap

+10

Một luồng số nguyên bắt đầu bằng các giá trị trong nums. Sau đó, các giá trị trong adds lần lượt xuất hiện. Sau mỗi lần xuất hiện, ghi lại giá trị lớn thứ k trong tất cả các giá trị đã thấy, tính riêng các giá trị bằng nhau. Trả về các giá trị đã ghi theo thứ tự, mỗi giá trị tương ứng với một giá trị trong adds.

nums chứa ít nhất k-1 giá trị, vì vậy sau lần xuất hiện đầu tiên, luôn có ít nhất k giá trị để chọn.

Hàm

kthLargestStream(k: integer, nums: integer-array, adds: integer-array) → integer-array

kinteger: thứ hạng cần báo cáo, 1 là giá trị lớn nhất
numsinteger-array: các giá trị đã có trong luồng
addsinteger-array: các giá trị được đưa vào theo thứ tự
Trả vềinteger-array: giá trị lớn thứ k sau mỗi lần xuất hiện

Ràng buộc

1 ≤ nums.length ≤ 10⁴
1 ≤ adds.length ≤ 10⁴
1 ≤ k ≤ nums.length + 1
-10⁴ ≤ nums[i], adds[i] ≤ 10⁴
nums có thể theo bất kỳ thứ tự nào, và các giá trị (value) bằng nhau vẫn được tính riêng.

Ví dụ

Đầu vào: k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
Đầu ra: [3, 5, 6, 6, 7]
Giải thích: Sau 3, số lớn thứ ba trong các số 7, 5, 3 và 1 là 3. Tiếp theo, 9 nâng số này lên 5, 6 nâng lên 6, 2 không làm thay đổi gì, và 8 nâng lên 7 (9, 8, 7).

Đầu vào: k = 1nums = [-2]adds = [-5, 0, -1, 4]
Đầu ra: [-2, 0, 0, 4]
Giải thích: Với k = 1, đáp án là giá trị lớn nhất tính đến thời điểm đó: -2 cho đến khi 0 xuất hiện, vẫn là 0 sau -1, rồi đến 4.

Câu hỏi mở rộng

Nếu có thể xóa các giá trị khỏi luồng dữ liệu, bạn sẽ trả lời câu hỏi tương tự như thế nào?

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

Các giá trị không bao giờ rời khỏi luồng, nên giá trị nào thấp hơn giá trị lớn thứ k hiện tại sẽ bị loại hẳn. Chỉ giữ lại k giá trị lớn nhất trong một đống tối thiểu: phần tử trên cùng là đáp án, và mỗi giá trị mới đến cần một phép so sánh cùng tối đa một lần cập nhật đống với độ phức tạp O(log k).

Sắp xếp sau mỗi lần đến

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Giữ mọi giá trị trong một danh sách. Sau mỗi lần thêm, sắp xếp danh sách theo thứ tự tăng dần rồi đọc chỉ số length-k, theo định nghĩa đó là phần tử lớn thứ k.

Mỗi lần thêm sẽ sắp xếp tối đa n + m giá trị, trong đó n và m là độ dài của nums và adds. Với 10^4 phần tử mỗi danh sách, tổng cộng sẽ có khoảng 2 × 10^9 phép so sánh.

Thuật toán

Sao chép nums vào danh sách values.
Với mỗi giá trị của adds, thêm giá trị đó vào values.
Sắp xếp values theo thứ tự tăng dần và ghi lại values[length-k].
Trả về các giá trị đã ghi lại.

def kthLargestStream(k, nums, adds):
    values = list(nums)
    result = []
    for x in adds:
        values.append(x)
        values.sort()
        # In increasing order the k-th largest sits k places from the end.
        result.append(values[len(values) - k])
    return result

Min-heap gồm k giá trị lớn nhất

Ý tưởng

Khi một giá trị có k giá trị lớn hơn đứng trên nó, điều đó vẫn đúng trong phần còn lại của luồng, vì vậy chỉ cần quan tâm đến k giá trị lớn nhất đã thấy cho đến lúc đó. Lưu chúng vào một đống min. Phần tử trên cùng là giá trị nhỏ nhất trong k giá trị lớn nhất, chính là giá trị lớn thứ k trong toàn bộ các giá trị.

Khi x xuất hiện và đống đã đầy, hãy so sánh nó với phần tử trên cùng. Nếu x không lớn hơn, nó không thuộc k giá trị lớn nhất nên không có gì thay đổi. Nếu nó lớn hơn, phần tử trên cùng bị loại: thay thế phần tử đó bằng x rồi sàng xuống, trong O(log k). Các giá trị ban đầu cũng được xử lý theo cách tương tự, vì vậy nums có thể dài hơn k.

Trong ví dụ đầu tiên, sau khi xử lý nums, đống chứa 7, 1 và 5, với 1 ở trên cùng. Giá trị 3 xuất hiện và thay thế 1; phần tử trên cùng lúc này là 3, đáp án đầu tiên.

Thuật toán

Bắt đầu với một đống tối thiểu rỗng.
Để thêm x: nếu đống chứa ít hơn k giá trị, hãy đẩy x vào. Nếu không, nếu x lớn hơn phần tử đầu, hãy thay phần tử đầu bằng x và khôi phục thứ tự của đống.
Thêm mọi giá trị của nums theo cách này.
Với mỗi giá trị của adds, hãy thêm giá trị đó và ghi lại phần tử đầu của đống.
Trả về các giá trị đã ghi lại.

import heapq


def kthLargestStream(k, nums, adds):
    # A min-heap of the k largest values so far; heap[0] is the smallest of them.
    heap = []

    def add(x):
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x

    for x in nums:
        add(x)
    result = []
    for x in adds:
        add(x)
        result.append(heap[0])  # the k-th largest so far
    return result

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

Loại bỏ các giá trị trùng lặp. Bốn giá trị lớn nhất trong 9, 6, 6, 6, 2 là 9, 6, 6 và 6. Tập hợp hoặc cách kiểm tra bỏ qua các giá trị đã xuất hiện sẽ trả về 2 ở ví dụ thứ ba thay vì 6.
Đọc đáp án trước khi thêm. Khi nums chứa k-1 giá trị, đống chỉ đầy sau khi phần tử đầu tiên được thêm vào, vì vậy hãy thêm trước rồi đọc giá trị trên cùng.
Đếm từ đầu sai sau khi sắp xếp. Theo thứ tự tăng dần, giá trị lớn thứ k nằm ở chỉ số length-k; chỉ số k-1 chứa giá trị nhỏ thứ k.
Dùng thứ tự mặc định của đống. priority_queue của C++ và BinaryHeap của Rust là đống cực đại: truyền greater<int> hoặc bọc các giá trị trong Reverse.

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

Tại sao dùng đống nhỏ nhất thay vì đống lớn nhất để tìm phần tử lớn thứ k?

Giá trị nhỏ nhất trong số k giá trị lớn nhất vừa là đáp án, vừa là giá trị mà một phần tử mới phải vượt qua, và một đống tối thiểu có kích thước k sẽ giữ giá trị đó ở trên cùng. Một đống tối đa chứa mọi giá trị sẽ đưa giá trị lớn nhất lên trên cùng, nên để đến giá trị thứ k, bạn phải lấy ra k-1 giá trị rồi đưa chúng trở lại mỗi khi có phần tử mới.

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

Mỗi lần phần tử đến có chi phí O(log k): một lần so sánh với phần tử trên cùng và nhiều nhất một lần sàng qua một đống gồm k giá trị. Việc tạo đống từ nums có chi phí O(n log k), vì vậy toàn bộ quá trình chạy mất O((n + m) log k) thời gian và cần thêm O(k) không gian.

Có thể giải bài toán phần tử lớn thứ K trong luồng dữ liệu bằng danh sách đã sắp xếp không?

Có. Giữ tất cả giá trị theo thứ tự đã sắp xếp, chèn mỗi giá trị mới vào đúng vị trí bằng tìm kiếm nhị phân, rồi đọc giá trị cách cuối danh sách k vị trí. Việc tìm kiếm có độ phức tạp O(log n), nhưng việc dịch chuyển các giá trị sau vị trí chèn có độ phức tạp O(n) cho mỗi giá trị mới: khoảng 1.5 × 10^8 lần dịch chuyển với 10^4 giá trị ban đầu và 10^4 giá trị mới.

def kthLargestStream(k, nums, adds):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

k = 3
nums = [7, 1, 5]
adds = [3, 9, 6, 2, 8]

Đầu ra mong đợi

[3, 5, 6, 6, 7]