C++LeetCode 구현(23.k 개의 질서 있 는 링크 통합)

[LeetCode]23.Merge k Sorted Lists 합병 k 개 질서 있 는 링크
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
이 문 제 는 k 개의 질서 있 는 링크 를 합병 시 키 고 최종 적 으로 합 친 결과 도 질서 가 있어 야 합 니 다.전에 한 가지 했 습 니 다.  Merge Two Sorted Lists두 개의 질서 있 는 링크 를 혼합 하여 삽입 하 는 것 입 니 다.이 문 제 는 난이 도 를 증가 시 켜 k 개의 질서 있 는 링크 를 합병 하 는 것 이 되 었 으 나 몇 개 를 합병 하 든 기본적으로 두 개 를 합병 해 야 한다.그렇다면 우선 그 문제 의 해법 을 이용 해 풀 수 있 을 지 고민 이다.답 은 긍정 적 이지 만 수정 이 필요 합 니 다.어떻게 수정 해 야 합 니까?가장 먼저 생각 나 는 것 은 두 개의 합병 입 니 다.바로 앞의 두 개 를 먼저 합병 하고 세 번 째 와 합 친 다음 에 네 번 째 는 k 개 까지 입 니 다.이러한 사고방식 은 옳 지만 효율 이 높 지 않 아 OJ 를 통과 할 수 없 기 때문에 사고방식 을 바 꿀 수 밖 에 없다.여 기 는 분 치 법 Divide and Conquer Approach 를 사용 해 야 한다.쉽게 말 하면 쉬 지 않 고 반 으로 나 누 는 것 이다.예 를 들 어 k 개의 링크 는 먼저 두 개의 k/2 개의 링크 를 합병 하 는 임무 로 나 누고 한 개 또는 두 개의 링크 만 있 는 임무 로 나 눌 때 까지 계속 아래로 나 누 어 합병 하기 시작한다.예 를 들 어 6 개의 링크 를 합병 하면 분 치 법 에 따라 먼저 0 과 3,1 과 4,2 와 5 를 합병 한다.이렇게 되면 다음 에는 3 개의 링크 를 합 쳐 1 과 3 을 합 쳐 마지막 에 2 와 합병 하면 된다.코드 중의 k 는(n+1)/2 를 통 해 계 산 된 것 입 니 다.여기 서 왜 1 을 추가 해 야 합 니까?이것 은 n 이 홀수 일 때 k 는 항상 후반 부 부터 시작 할 수 있 습 니 다.예 를 들 어 n=5 일 때 k=3 은 0 과 3 이 합 쳐 지고 1 과 4 가 합 쳐 지 며 가장 중간 에 있 는 2 가 비어 있 습 니 다.n 이 짝수 일 때 1 을 더 해도 영향 을 주지 않 습 니 다.예 를 들 어 n=4 일 때 k=2,그러면 0 과 2 가 합병 되 고 1 과 3 이 합병 되 어 문 제 를 완벽 하 게 해결 합 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return NULL;
        int n = lists.size();
        while (n > 1) {
            int k = (n + 1) / 2;
            for (int i = 0; i < n / 2; ++i) {
                lists[i] = mergeTwoLists(lists[i], lists[i + k]);
            }
            n = k;
        }
        return lists[0];
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if (l1) cur->next = l1;
        if (l2) cur->next = l2;
        return dummy->next;
    }
};

우 리 는 또 다른 해법 을 살 펴 보 자.이런 해법 은 최소 더미 라 는 데이터 구 조 를 이용 했다.먼저 k 개의 링크 의 첫 번 째 요 소 를 최소 더미 에 넣 으 면 자동 으로 순 서 를 배열 할 것 이다.그 다음 에 가장 작은 요 소 를 꺼 내 서 최종 결과 의 링크 에 넣 은 다음 에 요 소 를 꺼 내 서 다음 요 소 를 더미 에 넣 습 니 다.다음 에 더미 에서 가장 작은 요 소 를 꺼 내 똑 같은 조작 을 합 니 다.이런 식 으로 유추 하면 더미 에 요소 가 없 을 때 까지 k 개의 링크 도 하나의 링크 로 합 쳐 첫 번 째 노드 로 돌아 가면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](ListNode*& a, ListNode*& b) {
            return a->val > b->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp) > q(cmp);
        for (auto node : lists) {
            if (node) q.push(node);
        }
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        while (!q.empty()) {
            auto t = q.top(); q.pop();
            cur->next = t;
            cur = cur->next;
            if (cur->next) q.push(cur->next);
        }
        return dummy->next;
    }
};

아래 의 이러한 해법 은 혼합 정렬 사상 을 이용 하 였 으 며,분 치 법의 하나 에 속한다.방법 은 원 링크 를 두 단락 으로 나 눈 다음 에 각 단락 에 재 귀 함 수 를 호출 하 는 것 이다.suppose 가 돌아 온 left 와 right 는 이미 합 친 다음 에 left 와 right 를 합병 하 는 것 이다.합병 하 는 방법 은 이전의 그 방법 을 사용 하 는 것 이다.  Merge Two Sorted Lists  중의 임의의 해법 을 사용 하면 됩 니 다.여 기 는 재 귀적 인 문법 을 사 용 했 고 본 문제 의 해법 중 하 나 는 교체 적 인 문법 을 사 용 했 습 니 다.코드 는 다음 과 같 습 니 다.
해법 3:

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return helper(lists, 0, (int)lists.size() - 1);
    }
    ListNode* helper(vector<ListNode*>& lists, int start, int end) {
        if (start > end) return NULL;
        if (start == end) return lists[start];
        int mid = start + (end - start) / 2;
        ListNode *left = helper(lists, start, mid);
        ListNode *right = helper(lists, mid + 1, end);
        return mergeTwoLists(left, right);
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

아래 의 이런 해법 은 계수 정렬 사상 을 이용 했다.사고방식 은 모든 결점 값 이 나타 나 는 최대 값 과 최소 값 을 기록 한 다음 에 모든 결점 값 이 나타 나 는 횟수 를 기록 하 는 것 이다.그러면 최소 값 에서 최대 값 으로 옮 겨 다 닐 때 순서대로 모든 결점 값 을 거 쳐 나타 나 는 횟수 에 따라 상대 적 인 개수 의 결점 을 구축한다.그러나 이런 해법 은 특히 주의해 야 할 부분 이 있 습 니 다.그것 은 합병 후의 링크 노드 가 모두 재 구축 되 었 다 는 것 입 니 다.만약 에 어떤 상황 에서 결점 을 새로 만 들 지 못 하고 교환 하거나 다시 연결 할 수 밖 에 없다 면 이 해법 은 사용 할 수 없 지만 다행히 본 문 제 는 이러한 제한 이 없 기 때문에 OJ 를 완벽 하 게 통과 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다.
해법 4:

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        unordered_map<int, int> m;
        int mx = INT_MIN, mn = INT_MAX;
        for (auto node : lists) {
            ListNode *t = node;
            while (t) {
                mx = max(mx, t->val);
                mn = min(mn, t->val);
                ++m[t->val];
                t = t->next;
            }
        }
        for (int i = mn; i <= mx; ++i) {
            if (!m.count(i)) continue;
            for (int j = 0; j < m[i]; ++j) {
                cur->next = new ListNode(i);
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};

C++구현 LeetCode(23.합병 k 개 질서 있 는 링크)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++합병 k 개 질서 있 는 링크 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!