leetcode C++ 23. K個のソートチェーンテーブルをマージk個のソートチェーンテーブルをマージし、マージ後のソートチェーンテーブルを返します.アルゴリズムの複雑さを分析して説明してください.

1955 ワード

一、考え方:
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;  
    }
};