Çeşidlənmiş Siyahıları birləşdirin Leetcode Həll

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Facebook google Həqiqətən LinkedIn microsoft Kahin Sprinklr VMware Yandex
Bölün və fəth edin Yığın Bağlı siyahı Mağaza tiktok TuSimple Walmart Qlobal texnologiyaBaxılıb 47

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The Çeşidlənmiş Siyahıları birləşdirin LeetCode Həlli – “Merge k Sorted Lists” massivi verildiyini bildirir k bağlı siyahılar, burada hər bir əlaqəli siyahının öz dəyərləri var artan qaydada sıralanır. Etməliyik bütün k ilə əlaqəli siyahıları birləşdirin bir əlaqəli siyahıya daxil edin və geri qaytarın baş əlaqəli siyahıdan.

Misal:

Input:  lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Explanation:

  • Bütün dəyərləri artan qaydada nəzərdən keçirin: [1, 1, 2, 3, 4, 4, 5, 6].
  • Yuxarıdakı dəyərlərlə əlaqəli siyahı yaratmalıyıq.
Input:  lists = []
Output: []

Explanation:

  • Giriş massivi boşdur, əlaqəli siyahının başı olaraq null göstəricisini qaytarın.

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Prioritet növbə.
  2. Əlaqədar siyahılar massivində təkrarlayın və hamısını saxlayın cütlər {dəyərlər, baş göstəricilər} ci yığın.
  3.  Hər dəfə, minimum dəyəri olan nodu çıxarın min-yığından və onu düzəldin növbəti qovşaq yeni yaradılmış əlaqəli siyahıdan.
  4. Həmçinin, yoxlayın atılan node növbəti node varsa, Sonra cütü daxil edin {dəyər, növbəti node} yenə min yığınında.
  5. Yuxarıda qeyd olunan proses, bütün dəyərlərin artan qaydada çeşidləndiyi yeni əlaqəli siyahının formalaşması ilə nəticələnir, çünki biz hər dəfə minimum dəyərlə qovşağı çıxarırıq və onu yeni əlaqəli siyahının növbəti qovşağına edirik.
  6. Nəhayət, k bağlı siyahıları birləşdirdik.

Kodu

k Çeşidlənmiş Siyahıları birləşdirin Leetcode C++ Həlli:

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()){
            return nullptr;
        }
        ListNode* dummy = new ListNode(0);
        ListNode* head = dummy;
        priority_queue<pair<int,ListNode*>,vector<pair<int,ListNode*>>,greater<pair<int,ListNode*>>> pq;
        for(auto& node:lists){
            if(node!=nullptr){
                pq.push({node->val,node});
            }
        }
        while(!pq.empty()){
            ListNode* node = pq.top().second;
            pq.pop();
            if(node->next!=nullptr){
                pq.push({node->next->val,node->next});
            }
            dummy->next = node;
            dummy = node;
        }
        return head->next;
    }
};

Çeşidlənmiş Siyahıları birləşdirin Leetcode Java Həlli:

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0){
            return null;
        }
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.length, (a,b)-> a.val-b.val);
        for(ListNode node:lists){
            if(node!=null){
                pq.add(node);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while(!pq.isEmpty()){
            ListNode node = pq.poll();
            if(node.next!=null){
                pq.add(node.next);
            }
            dummy.next = node;
            dummy = node;
        }
        return head.next;
    }
}

Çeşidlənmiş Siyahıların Birləşdirilməsi üçün Mürəkkəblik Təhlili Leetcode Həlli

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O(NKlogK). Hər bir qovşaq bir dəfə min yığına itələnir və cəmi var ən çox N*K əlaqəli siyahıların verilmiş massivindəki qovşaqlar, burada N = tək əlaqəli siyahıdakı qovşaqların maksimum sayı və K = əlaqəli siyahının massivinin ölçüsü.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi TAMAM) çünki biz maksimum k ölçüsündə min yığından istifadə edirik.

 

İstinad: - https://en.wikipedia.org/wiki/Linked_list

Crack Sistemi Dizayn Müsahibələri
Translate »