ບັນຊີລາຍຊື່ການເຊື່ອມໂຍງ K Sorted  


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ByteDance ຖານຂໍ້ມູນ eBay ເຟສບຸກ Goldman Sachs Microsoft Oracle Palantir Technologies Twitter Uber ຕ້ອງການ
ແບ່ງແລະເອົາຊະນະ ຂີ້ເຫຍື້ອ ບັນຊີທີ່ເຊື່ອມໂຍງ

ຈັດປະເພດ K ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ ບັນຫາແມ່ນມີຊື່ສຽງເທົ່າກັບຈຸດ ສຳ ພາດຂອງການເບິ່ງ. ຄຳ ຖາມນີ້ຖາມຫຼາຍຄັ້ງໃນບໍລິສັດໃຫຍ່ໆເຊັ່ນ Google, Microsoft, Amazon, ແລະອື່ນໆ. ໃນຖານະທີ່ຊື່ດັ່ງກ່າວຊີ້ໃຫ້ເຫັນວ່າພວກເຮົາໄດ້ຮັບລາຍຊື່ k ທີ່ເຊື່ອມໂຍງເຂົ້າມາ. ພວກເຮົາຕ້ອງລວມເອົາພວກມັນເຂົ້າກັນເປັນກ ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງດຽວ.

ຂໍໃຫ້ພິຈາລະນາຄະດີການທົດສອບຕົວຢ່າງເພື່ອໃຫ້ເຂົ້າໃຈມັນດີຂື້ນ:

ຍົກຕົວຢ່າງ  

ການປ້ອນຂໍ້ມູນ

[

1-> 2-> 3,

1-> 4-> 6,

2-> 3

]

ຜົນຜະລິດ

1->1->2->2->3->3->4->6

ວິທີການ -1 ສຳ ລັບລາຍຊື່ການເຊື່ອມໂຍງ Merge K Sorted  

ຜົນບັງຄັບໃຊ້ສັດ 

  • ລອກເອົາບັນດາລາຍຊື່ທີ່ເຊື່ອມໂຍງທັງ ໝົດ ແລະໃສ່ທຸກຄ່າໃນ Array / ArrayList / Vector (ບໍ່ວ່າບ່ອນໃດກໍ່ຕາມທີ່ທ່ານສາມາດຊອກຫາໄດ້ງ່າຍ)
  • ຈັດຮຽງຂໍ້ມູນ
  • ສ້າງລາຍຊື່ທີ່ເຊື່ອມໂຍງ ໃໝ່ ຈາກຂໍ້ມູນທີ່ຈັດຮຽງ

Voila! ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງແລະຈັດລຽງປະເພດຂອງພວກເຮົາແມ່ນກຽມພ້ອມແລ້ວ. ໃຫ້ເຂົ້າໃຈວ່າດີກວ່າໂດຍລະຫັດ.

ໂຄງການ Java

class Solution 
{
    public ListNode mergeKLists(ListNode[] lists) 
    {
        ListNode aux=new ListNode(0);
        List<Integer>lisa=new ArrayList<Integer>();
        for(int i=0;i<lists.length;i++)
        {
            ListNode ptr=lists[i];
            while(ptr!=null)
            {
                lisa.add(ptr.val);
                ptr=ptr.next;
            }
        }
        Collections.sort(lisa);
        ListNode ptr=aux;
        for(int i=0;i<lisa.size();i++)
        {
            ListNode temp=new ListNode(lisa.get(i));
            temp.next=null;
            ptr.next=temp;
            ptr=ptr.next;
        }
        return aux.next;
    }
}

ໂຄງການ C ++

class Solution 
{
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
    vector<int>store;
    for(int i=0;i<lists.size();i++)
        {
            ListNode *ptr=lists[i];
            while(ptr!=NULL)
            {
                store.push_back(ptr->val);
                ptr=ptr->next;
            }
        }
        sort(store.begin(),store.end());
        ListNode *ptr=new ListNode();
        ListNode *aux=ptr;
        for(int i=0;i<store.size();i++)
        {
            ListNode *temp=new ListNode(store[i]);
            temp->next=NULL;
            ptr->next=temp;
            ptr=ptr->next;
        }
        return aux->next;
    }
};
[

1->2->3,

1->4->6,

2->3

]
1->1->2->2->3->3->4->6

ການວິເຄາະຄວາມສັບສົນ

ຕອນນີ້ໃຫ້ພວກເຮົາພິຈາລະນາຄວາມສັບສົນຂອງເວລາຂອງການແກ້ໄຂຂ້າງເທິງນີ້:

ເບິ່ງ
ຂຽນ ໜ້າ ທີ່ເພື່ອຈຸດທີ່ຕັດກັນຂອງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງ

ເວລາຖືກປະຕິບັດ ສຳ ລັບຄວາມຫຼົງໄຫຼແລະການສ້າງ: O (n)

ເວລາຖືກປະຕິບັດ ສຳ ລັບການຈັດຮຽງ: O (n log n)

ເຮັດໃຫ້ເວລາສັບສົນ: O (n log n)

ວິທີການ -2 ສຳ ລັບລາຍຊື່ການເຊື່ອມໂຍງ Merge K Sorted  

ການໃຊ້ Min-Heap

A ແຖວບູລິມະສິດສາມາດຖືກນໍາໃຊ້ເປັນບ່ອນເກັບມ້ຽນ

ຂໍ້​ດີ​:

  • ບໍ່ ຈຳ ເປັນຕ້ອງຈັດຮຽງ

ໃຫ້ພວກເຮົາເບິ່ງຄືກັນກັບການຊ່ວຍເຫຼືອຂອງລະຫັດ

ໂຄງການ Java

class Solution 
{
    public ListNode mergeKLists(ListNode[] lists)
    {
    Queue<Integer>store=new PriorityQueue();
    for(int i=0;i<lists.length;i++)
    {
        ListNode ptr=lists[i];
        while(ptr!=null)
        {
            store.add(ptr.val);
            ptr=ptr.next;
        }
    }
    if(store.isEmpty() )    
        return null;
    ListNode head=new ListNode(store.poll());
    ListNode cur=head;
    while(!store.isEmpty())
    {
        ListNode temp=new ListNode(store.poll());
        cur.next=temp;
        cur=cur.next;
    }
    return head;
    }
}
[
2->5->7->9,
1->2->3->->10
]
1->2->2->3->5->7->9->10

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນຂອງເວລາຂອງສິ່ງຂ້າງເທິງ: O (n log n)

ວິທີການ -3 ສຳ ລັບລາຍຊື່ການເຊື່ອມໂຍງ Merge K Sorted  

ແບ່ງແລະເອົາຊະນະ

  • ຂັ້ນຕອນການແບ່ງຂັ້ນ

OBJECTIVE- ບອກລາຍຊື່ k ເພື່ອປະສົມປະສານ ໜ້າ ທີ່ k / 2 ໃນເວລາ

  • The Merge ບາດກ້າວ

ເປົ້າ ໝາຍ -ເພື່ອພິຈາລະນາຄຸນຄ່າທີ່ນ້ອຍກວ່າແລະເພີ່ມພວກມັນເພື່ອສ້າງລາຍຊື່ ໃໝ່

    • ສ້າງຕົວຊີ້ເພື່ອສົ່ງຄືນລາຍການລວມ
    • ຕື່ມມູນຄ່ານ້ອຍລົງຈາກບັນຊີລາຍຊື່ທັງສອງ
    • ຕົວຊີ້ວັດທີ່ເພີ່ມຂື້ນຈາກມູນຄ່າທີ່ໄດ້ຖືກປະຕິບັດ
    • ກັບຄືນລາຍການທີ່ເຊື່ອມໂຍງແລະຈັດລຽງ ລຳ ດັບຈາກສອງລາຍການ
ບັນຊີລາຍຊື່ການເຊື່ອມໂຍງ K Sorted
ການສະແດງການລວມເຂົ້າ ສຳ ລັບລາຍຊື່ສອງສາມລາຍການ

ໃຫ້ເຂົ້າໃຈວ່າດີກວ່າດ້ວຍການຊ່ວຍເຫຼືອຂອງລະຫັດ

ໂຄງການ Java

class Solution 
{
    public static ListNode merge(ListNode l1,ListNode l2)
    {
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        ListNode aux=new ListNode();
        ListNode head=aux;
        while(l1!=null && l2!=null)
        {
            if(l1.val>l2.val)
            {
                aux.next=l2;
                l2=l2.next;
            }
            else 
            {
                aux.next=l1;
                l1=l1.next;
            }
            aux=aux.next;
        }
        if(l1!=null)
            aux.next=l1;
        else if(l2!=null)
            aux.next=l2;
        return head.next;
    }
    public static ListNode divide(ListNode[]lists,int start,int end)
    {
        if(end<start)
            return null;
        if(end==start)
            return lists[start];
        int mid=start+(end-start)/2;
        return(merge(divide(lists,start,mid),divide(lists,mid+1,end)));
    }
    public ListNode mergeKLists(ListNode[] lists)
    {
     if(lists == null) 
         return null;
     if(lists.length == 1) 
         return lists[0];
     return divide(lists,0,lists.length-1);   
    }
}

ໂຄງການ C ++

class Solution 
{
  public:
    ListNode* merge(ListNode *l1,ListNode *l2)
    {
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        ListNode *aux=new ListNode();
        ListNode *head=aux;
        while(l1!=NULL && l2!=NULL)
        {
            if(l1->val>l2->val)
            {
                aux->next=l2;
                l2=l2->next;
            }
            else 
            {
                aux->next=l1;
                l1=l1->next;
            }
            aux=aux->next;
        }
        if(l1!=NULL)
            aux->next=l1;
        else if(l2!=NULL)
            aux->next=l2;
        return head->next;
    }
    public:
    ListNode* divide(vector<ListNode*>&lists,int start,int end)
    {
        if(end<start)
            return NULL;
        if(end==start)
            return lists[start];
        int mid=start+(end-start)/2;
        return(merge(divide(lists,start,mid),divide(lists,mid+1,end)));
    }
    public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
     if(lists.size() == 0) 
         return NULL;
     if(lists.size() == 1) 
         return lists[0];
     return divide(lists,0,lists.size()-1);   
    }
};
[
1->2,
3,
4->5->6->7,
8->9->10,
11
]
1->2->3->4->5->6->7->8->9->10->11

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນຂອງເວລາ = O (n log n)

ເບິ່ງ
ລະບົບ Algorithm ຂອງ Bellman Ford

ຄວາມສັບສົນໃນພື້ນທີ່ = O (1)

ເອກະສານ