leetcode C++ 23. K個のソートチェーンテーブルをマージk個のソートチェーンテーブルをマージし、マージ後のソートチェーンテーブルを返します.アルゴリズムの複雑さを分析して説明してください.
一、考え方:
1つ目は、各チェーンテーブルの最小値を求め、このノードをマージした結果チェーンテーブルの中に配置します.このチェーンテーブルはnextを指します.
第2種:優先度キュー、ヘッダノードを優先度キューに入れ、topの1つを合併したチェーンテーブルに入れ、topがnextを指し、pushがキューに入る
二、コード
第一の考え方:
第二の考え方:出所:https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/c-you-xian-dui-lie-liang-liang-he-bing-fen-zhi-he-/
1つ目は、各チェーンテーブルの最小値を求め、このノードをマージした結果チェーンテーブルの中に配置します.このチェーンテーブルはnextを指します.
第2種:優先度キュー、ヘッダノードを優先度キューに入れ、topの1つを合併したチェーンテーブルに入れ、topがnextを指し、pushがキューに入る
二、コード
第一の考え方:
class Solution {
public:
ListNode *insert(ListNode *nowNode, int val) {
if (nowNode == NULL)
return new ListNode(val);
else {
nowNode->next = new ListNode(val);
return nowNode->next;
}
}
ListNode* mergeKLists(vector& lists) {
ListNode *res = NULL, *nowNode = res;
while (true) {
bool isAllNull = true;
int minVal = INT_MAX, pos = -1;
for (int i = 0; i < lists.size(); i++)
{
if (lists[i] != NULL) {
isAllNull = false;
if (lists[i]->val < minVal) {
pos = i;
minVal = lists[i]->val;
}
}
}
if (isAllNull)
return res;
lists[pos] = lists[pos]->next;
if (nowNode == NULL)
res = nowNode = insert(nowNode, minVal);
else
nowNode = insert(nowNode, minVal);
}
return res;
}
};
第二の考え方:出所:https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/c-you-xian-dui-lie-liang-liang-he-bing-fen-zhi-he-/
class Solution {
public:
//
struct cmp{
bool operator()(ListNode *a,ListNode *b){
return a->val > b->val;
}
};
ListNode* mergeKLists(vector& lists) {
priority_queue, cmp> pri_queue;
// k
for(auto elem : lists){
if(elem) pri_queue.push(elem);
}
// /
ListNode dummy(-1);
ListNode* p = &dummy;
//
while(!pri_queue.empty()){
ListNode* top = pri_queue.top(); pri_queue.pop();
p->next = top; p = top;
if(top->next) pri_queue.push(top->next);
}
return dummy.next;
}
};