Merge k Sorted Lists

Q: Độ phức tạp thời gian của Merge k Sorted Lists là bao nhiêu?

Với min-heap, độ phức tạp là O(N log k) , trong đó N là tổng số giá trị và k là số danh sách. Mỗi giá trị được thêm vào rồi lấy ra một lần, và heap chứa tối đa k mục. Bộ nhớ bổ sung là O(k) , ngoài phần bộ nhớ dành cho đầu ra.

Q: Tại sao không gom tất cả giá trị lại rồi sắp xếp?

Điều đó đúng và mất thời gian O(N log N) . Cách này bỏ qua việc các danh sách đã được sắp xếp, nên mất log N cho mỗi giá trị, trong khi heap chỉ mất log k , đồng thời cần lưu mọi giá trị trong bộ nhớ cùng lúc. Heap cũng có thể hợp nhất các danh sách được gửi đến dưới dạng luồng.

KhóHeap Danh sách liên kết

+10

Bạn nhận được k danh sách số nguyên làm các hàng của lists. Mỗi hàng được sắp xếp theo thứ tự không giảm, các hàng có thể có độ dài khác nhau và không hàng nào rỗng.

Gộp chúng thành một danh sách chứa mọi giá trị từ tất cả các hàng, được sắp xếp theo thứ tự không giảm, rồi trả về danh sách đó. Giá trị xuất hiện nhiều lần trong một hàng hoặc nhiều hàng sẽ xuất hiện đúng số lần đó trong kết quả.

Hàm

mergeKLists(lists: integer-2d-array) → integer-array

listsinteger-2d-array: các danh sách đã sắp xếp, mỗi hàng một danh sách, có thể có độ dài khác nhau
Trả vềinteger-array: mọi giá trị từ mọi hàng, trong một danh sách đã sắp xếp

Ràng buộc

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length, và tổng số giá trị trong tất cả các hàng không vượt quá 10⁴
-10⁴ ≤ lists[i][j] ≤ 10⁴
Mỗi hàng được sắp xếp theo thứ tự không giảm.

Ví dụ

Đầu vào: lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
Đầu ra: [1, 2, 3, 4, 5, 6, 9, 10]
Giải thích: Các hàng bắt đầu bằng 2, 1 và 3, nên 1 đứng đầu tiên. Tiếp theo, các phần tử đầu hàng là 2, 4 và 3, nên 2 đứng tiếp theo, cứ thế tiếp tục. Hàng thứ ba hết phần tử sau 5, còn lại 6, 9 và 10.

Đầu vào: lists = [[5], [-2, 5, 7], [0, 5]]
Đầu ra: [-2, 0, 5, 5, 5, 7]
Giải thích: Ba số 5 đến từ ba hàng khác nhau và cả ba đều được giữ lại. Số âm -2 đứng trước 0 khi sắp xếp.

Câu hỏi mở rộng

Tìm khoảng (range) nhỏ nhất [a, b] chứa một giá trị từ mỗi hàng. Liệu một heap chứa các phần tử đầu hàng cùng với phần tử đầu hàng lớn nhất có thể làm được điều đó trong O(N log k) không?

Lời giải

Mỗi hàng đều đã được sắp xếp, vì vậy giá trị nhỏ nhất chưa dùng luôn là giá trị đầu tiên chưa dùng của một hàng nào đó, tức là phần tử đầu hàng. Quét tất cả k phần tử đầu hàng tốn k bước cho mỗi giá trị trong N giá trị. Một heap tối thiểu chứa các phần tử đầu hàng sẽ lấy ra giá trị nhỏ nhất trong O(log k), giúp giảm tổng thời gian từ O(N·k) xuống O(N log k).

So sánh tất cả k đầu cho mỗi giá trị

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

Ý tưởng

Giữ một chỉ số pos[r] ở đầu mỗi hàng. Mỗi lượt đọc tất cả các giá trị đầu hàng, thêm giá trị nhỏ nhất rồi tăng chỉ số của hàng đó: đây là bước trộn của merge sort, mở rộng từ hai danh sách thành k danh sách. Trong ví dụ đầu tiên, các giá trị đầu hàng lần lượt là 2, 1 và 3, nên 1 được đưa ra và giá trị đầu hàng thứ hai trở thành 4.

Mỗi trong số N giá trị cần quét qua tất cả k hàng. Với 10^4 hàng, mỗi hàng có một giá trị, ta cần kiểm tra hàng 10^8 lần.

Thuật toán

Đặt pos[r] = 0 cho mỗi hàng và đếm số giá trị, N.
Lặp lại N lần: xem từng hàng có pos[r] vẫn nằm trong hàng đó và ghi nhớ hàng có phần tử đầu tiên nhỏ nhất.
Thêm phần tử đầu tiên đó vào kết quả và tăng pos của hàng đó thêm 1.
Trả về kết quả.

def mergeKLists(lists):
    pos = [0] * len(lists)  # pos[r]: index of the first unused value in row r
    total = sum(len(row) for row in lists)
    merged = []
    for _ in range(total):
        best = -1  # the row whose head is the smallest so far
        for r in range(len(lists)):
            if pos[r] < len(lists[r]) and (best == -1 or lists[r][pos[r]] < lists[best][pos[best]]):
                best = r
        merged.append(lists[best][pos[best]])
        pos[best] += 1
    return merged

Min-heap gồm k nút đầu

Ý tưởng

Sau mỗi lần chọn, chỉ có một giá trị đầu hàng thay đổi, nhưng thao tác quét lại đọc toàn bộ k. Min-heap giữ các giá trị đầu hàng, với giá trị nhỏ nhất ở trên cùng. Gắn thẻ mỗi giá trị đầu hàng bằng số hàng của nó, để sau khi lấy (value, row) ra, bạn biết cần đưa giá trị tiếp theo của hàng nào vào. Heap luôn có một phần tử cho mỗi hàng còn giá trị, vì vậy phần tử trên cùng là giá trị chưa dùng nhỏ nhất.

Trong ví dụ đầu tiên, heap bắt đầu với 2, 1 và 3. Lấy 1 ra, đưa 4 vào. Lấy 2 ra, đưa 6 vào. Lấy 3 ra, đưa 5 vào. Lấy 4 ra, đưa 10 vào. Lấy 5 ra: hàng thứ ba đã hết giá trị, nên không đưa gì vào. Lấy 6 ra, đưa 9 vào, rồi lấy 9 và 10 ra.

Mỗi giá trị được đưa vào và lấy ra một lần, còn heap không bao giờ có nhiều hơn k phần tử: 2N thao tác, mỗi thao tác tốn O(log k). Với N = k = 10^4, số bước chưa đến 3 × 10^5. Heap dùng bộ nhớ O(k).

Thuật toán

Đưa (lists[r][0], r) của mọi hàng r vào một hàng đợi ưu tiên min-heap được sắp xếp theo giá trị.
Khi hàng đợi chưa rỗng, lấy cặp nhỏ nhất (value, r) ra và thêm value vào kết quả.
Nếu hàng r còn giá trị tiếp theo, hãy đưa giá trị đó cùng với r vào hàng đợi.
Trả về kết quả khi hàng đợi rỗng.

import heapq


def mergeKLists(lists):
    # The heap holds one (value, row) pair per row that still has values: that row's head.
    heap = [(row[0], r) for r, row in enumerate(lists)]
    heapq.heapify(heap)
    nxt = [1] * len(lists)  # nxt[r]: index of row r's next value, not yet in the heap
    merged = []
    while heap:
        value, r = heapq.heappop(heap)  # the smallest head of all rows
        merged.append(value)
        if nxt[r] < len(lists[r]):
            heapq.heappush(heap, (lists[r][nxt[r]], r))  # row r's new head takes its place
            nxt[r] += 1
    return merged

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

Đẩy các giá trị riêng lẻ vào. Sau khi lấy một giá trị ra, bạn không thể biết cần chuyển sang hàng nào. Hãy lưu cả hàng cùng với giá trị.
Vô tình dùng max-heap. C++ priority_queue và Rust BinaryHeap đặt giá trị lớn nhất lên đầu; hãy dùng greater<> hoặc Reverse.
Đẩy mọi giá trị vào ngay từ đầu. Kết quả vẫn được sắp xếp, nhưng heap sẽ tăng lên N phần tử và độ phức tạp công việc thành O(N log N).
Đọc quá cuối một hàng ngắn. Trong ví dụ đầu tiên, hàng thứ ba có hai giá trị, vì vậy hãy kiểm tra xem có giá trị tiếp theo hay không trước khi đẩy vào.
Bỏ các giá trị trùng lặp. Ba số 5 trong ví dụ thứ hai là các giá trị riêng biệt và tất cả đều phải có trong kết quả.

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

Độ phức tạp thời gian của Merge k Sorted Lists là bao nhiêu?

Với min-heap, độ phức tạp là O(N log k), trong đó N là tổng số giá trị và k là số danh sách. Mỗi giá trị được thêm vào rồi lấy ra một lần, và heap chứa tối đa k mục. Bộ nhớ bổ sung là O(k), ngoài phần bộ nhớ dành cho đầu ra.

Tại sao không gom tất cả giá trị lại rồi sắp xếp?

Điều đó đúng và mất thời gian O(N log N). Cách này bỏ qua việc các danh sách đã được sắp xếp, nên mất log N cho mỗi giá trị, trong khi heap chỉ mất log k, đồng thời cần lưu mọi giá trị trong bộ nhớ cùng lúc. Heap cũng có thể hợp nhất các danh sách được gửi đến dưới dạng luồng.

Bạn có thể trộn các danh sách đã sắp xếp mà không dùng heap không?

Đúng vậy, bằng cách chia để trị. Gộp các danh sách thành từng cặp bằng cách gộp hai danh sách, rồi gộp các kết quả thành từng cặp, cứ thế tiếp tục: có log k lượt, mỗi lượt duyệt qua mọi giá trị một lần, nên độ phức tạp là O(N log k). Gộp lần lượt từng danh sách vào một kết quả ngày càng lớn sẽ chậm hơn, với độ phức tạp O(N·k), vì các giá trị ở đầu bị sao chép lại trong mỗi lần gộp.

def mergeKLists(lists):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

lists = [[2, 6, 9], [1, 4, 10], [3, 5]]

Đầu ra mong đợi

[1, 2, 3, 4, 5, 6, 9, 10]