Bài 23 Leetcode: Merge k Sorted Lists

Đề bài:

Bạn được cho một mảng `lists` gồm k danh sách liên kết, mỗi danh sách được sắp xếp theo thứ tự tăng dần. Hợp nhất tất cả các danh sách liên kết thành một danh sách liên kết được sắp xếp và trả về nó.

Ví dụ 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Giải thích: Các danh sách liên kết là:
[
1->4->5,
1->3->4,
2->6
]
hợp nhất chúng thành một danh sách liên kết được sắp xếp:
1->1->2->3->4->4->5->6.

Ví dụ 2:

Input: lists = []
Output: []

Ví dụ 3:

Input: lists = [[]]
Output: []

Ràng buộc:

  • k == độ dài của lists
  • 0 <= k <= 10^4
  • 0 <= độ dài của lists[i] <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] được sắp xếp theo thứ tự tăng dần.
  • Tổng của độ dài các lists[i] sẽ không vượt quá 10^4.

Giải thích thuật toán bằng C++

class Solution {
 public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    auto compare = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> minHeap(
        compare);

    for (ListNode* list : lists)
      if (list != nullptr)
        minHeap.push(list);

    while (!minHeap.empty()) {
      ListNode* minNode = minHeap.top();
      minHeap.pop();
      if (minNode->next)
        minHeap.push(minNode->next);
      curr->next = minNode;
      curr = curr->next;
    }

    return dummy.next;
  }
};

Đây là một phương thức trong một lớp được gọi là `Solution`. Phương thức này được sử dụng để hợp nhất k danh sách liên kết thành một danh sách liên kết được sắp xếp.

Dưới đây là cách thuật toán hoạt động:

1. Phương thức `mergeKLists` nhận đầu vào là một vector `lists` chứa các con trỏ đến danh sách liên kết.

2. Khởi tạo một nút giả `dummy` với giá trị 0.

3. Khởi tạo một con trỏ `curr` trỏ tới `dummy`.

4. Định nghĩa một hàm so sánh `compare` để so sánh giá trị của hai nút liên kết. Hàm này sẽ trả về `true` nếu giá trị của nút thứ nhất lớn hơn giá trị của nút thứ hai.

5. Khởi tạo một hàng đợi ưu tiên `minHeap` để lưu trữ các con trỏ đến các nút liên kết. Hàng đợi này sẽ được sắp xếp theo thứ tự tăng dần dựa trên hàm so sánh `compare`.

6. Duyệt qua từng danh sách liên kết trong `lists` và đưa các con trỏ đến các nút đầu tiên của mỗi danh sách vào hàng đợi ưu tiên `minHeap`, trừ trường hợp danh sách đó là `nullptr`.

7. Trong khi hàng đợi ưu tiên `minHeap` không rỗng, thực hiện các bước sau:

a. Lấy nút có giá trị nhỏ nhất từ hàng đợi ưu tiên `minHeap`.

b. Loại bỏ nút đó khỏi hàng đợi ưu tiên.

c. Nếu nút đó có nút kế tiếp, đưa nút kế tiếp đó vào hàng đợi ưu tiên `minHeap`.

d. Gán con trỏ `curr->next` trỏ tới nút được lấy từ hàng đợi ưu tiên.

e. Di chuyển con trỏ `curr` tới nút tiếp theo trong danh sách liên kết.

8. Trả về con trỏ đến nút đầu tiên của danh sách liên kết đã hợp nhất.

Thuật toán này sử dụng hàng đợi ưu tiên để chọn nút có giá trị nhỏ nhất từ các danh sách liên kết. Bắt đầu bằng việc đưa các nút đầu tiên của mỗi danh sách vào hàng đợi ưu tiên. Sau đó, trong mỗi bước, ta lấy nút có giá trị nhỏ nhất từ hàng đợi ưu tiên, gán nút đó vào danh sách liên kết đã hợp nhất và di chuyển con trỏ `curr` tới nút tiếp theo. Nếu nút vừa lấy ra từ hàng đợi ưu tiên có nút kế tiếp, ta đưa nút đó vào hàng đợi ưu tiên để tiếp tục quá trình hợp nhất. Quá trình này diễn ra cho đến khi hàng đợi ưu tiên trống, và ta trả về danh sách liên kết đã hợp nhất.

Giải thích thuật toán bằng Java

class Solution {
  public ListNode mergeKLists(ListNode[] lists) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    Queue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);

    for (final ListNode list : lists)
      if (list != null)
        minHeap.offer(list);

    while (!minHeap.isEmpty()) {
      ListNode minNode = minHeap.poll();
      if (minNode.next != null)
        minHeap.offer(minNode.next);
      curr.next = minNode;
      curr = curr.next;
    }

    return dummy.next;
  }
}

Giải thích thuật toán bằng Python

from queue import PriorityQueue


class Solution:
  def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    dummy = ListNode(0)
    curr = dummy
    pq = PriorityQueue()

    for i, lst in enumerate(lists):
      if lst:
        pq.put((lst.val, i, lst))

    while not pq.empty():
      _, i, minNode = pq.get()
      if minNode.next:
        pq.put((minNode.next.val, i, minNode.next))
      curr.next = minNode
      curr = curr.next

    return dummy.next

 

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.