Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merge k Sorted Lists #46

Closed
Tracked by #100
fkdl0048 opened this issue Sep 30, 2024 · 1 comment
Closed
Tracked by #100

Merge k Sorted Lists #46

fkdl0048 opened this issue Sep 30, 2024 · 1 comment
Assignees
Labels
Milestone

Comments

@fkdl0048
Copy link
Owner

fkdl0048 commented Sep 30, 2024

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
using namespace std;

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* result = new ListNode();
        ListNode* dummy = result;

        while (true) {
            int minIndex = -1;
            int minValue = INT_MAX;

            for (int i = 0; i < lists.size(); i++) {
                if (lists[i] != nullptr && lists[i]->val < minValue) {
                    minValue = lists[i]->val;
                    minIndex = i;
                }
            }

            if (minIndex == -1) break;

            dummy->next = lists[minIndex];
            dummy = dummy->next;

            lists[minIndex] = lists[minIndex]->next;
        }

        return result->next;
    }
};
  • ListNode 연속 정렬 문제
  • 내 풀이는 앞 부분부터 읽어서 계속 병합하는 방식으로 풀이
  • 다른 솔루션들은 우선순위 큐를 많이 사용하는 듯 시간복잡도가 많이 낮아지는 것 같아서 아래 다시 풀이
struct Compare {
    bool operator()(ListNode* a, ListNode* b){
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Compare> minHeap;

        for (auto list : lists){
            if (list){
                minHeap.push(list);
            }
        }

        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;

        while(!minHeap.empty()){
            ListNode* smallestNode = minHeap.top();
            minHeap.pop();

            current->next = smallestNode;
            current = current->next;

            if (smallestNode->next){
                minHeap.push(smallestNode->next);
            }
        }

        return dummy->next;
    }
};
@fkdl0048 fkdl0048 mentioned this issue Sep 30, 2024
7 tasks
@fkdl0048 fkdl0048 self-assigned this Sep 30, 2024
@fkdl0048 fkdl0048 added this to Todo Sep 30, 2024
@github-project-automation github-project-automation bot moved this to Todo in Todo Sep 30, 2024
@fkdl0048 fkdl0048 added this to the LeetCode milestone Sep 30, 2024
@fkdl0048 fkdl0048 moved this from Todo to Two-Week Plan in Todo Sep 30, 2024
@fkdl0048 fkdl0048 closed this as completed Oct 4, 2024
@github-project-automation github-project-automation bot moved this from Two-Week Plan to Done in Todo Oct 4, 2024
@fkdl0048
Copy link
Owner Author

fkdl0048 commented Oct 4, 2024

복기

  • 앞 문제에서 2개의 배열을 정렬했다면, k개를 정렬해야 하기에 해당 로직 구현이 핵심
  • 내가 푼 풀이와 더 좋은 풀이의 차이를 이해

@fkdl0048 fkdl0048 mentioned this issue Oct 15, 2024
47 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
Status: Done
Development

No branches or pull requests

1 participant