Union ແລະ Intersection ຂອງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ຫ້ອງທົດລອງປະດິດສ້າງ 24 * 7 ຕິຊົມ Amazon Flipkart ສື່ມວນຊົນ Komli Microsoft Taxi4 ຮັບປະກັນ VMware ຫ້ອງທົດລອງ Walmart
Hash ບັນຊີທີ່ເຊື່ອມໂຍງ ຮຽງລໍາດັບ

ໃຫ້ສອງ ບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ, ສ້າງອີກສອງລາຍການທີ່ເຊື່ອມໂຍງກັນເພື່ອໃຫ້ໄດ້ສະຫະພາບແລະຈຸດເຊື່ອມຕໍ່ຂອງອົງປະກອບຂອງລາຍຊື່ທີ່ມີຢູ່.

ຍົກຕົວຢ່າງ

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

ບັນຊີລາຍຊື່ທີ 1: 5 → 9 → 10 → 12 → 14

ບັນຊີລາຍຊື່ທີ 2: 3 → 5 → 9 → 14 → 21

ຜົນໄດ້ຮັບ:

Intersection_list: 14 → 9 → 5

Union_list: 21 → 14 → 12 → 10 → 9 → 5 → 3

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

ລະບົບວິເຄາະ

  1. ສ້າງລາຍຊື່ທີ່ເຊື່ອມໂຍງໂດຍການປະກາດຫົວແລະຕົວຊີ້ຕໍ່ໄປຂອງບັນຊີ.
  2. ໃສ່ອົງປະກອບໃນທັງສອງລາຍການໂດຍໃຊ້ insert func.
  3. ຄັດທັງສອງລາຍການທີ່ເຊື່ອມໂຍງໂດຍໃຊ້ algorithm sort sortl.
  4. ສຸດທ້າຍ, ສະແກນເສັ້ນຊື່ທັງສອງລາຍຊື່ທີ່ຈັດຮຽງເພື່ອໃຫ້ໄດ້ສະຫະພາບແລະຕັດກັນຂອງບັນຊີ.

ຄໍາອະທິບາຍ

ກ່ອນອື່ນ ໝົດ, ພວກເຮົາສ້າງ Node ໂດຍການສ້າງຫ້ອງຮຽນ Node ໃນໂປແກມຂອງພວກເຮົາ, ເພື່ອວ່າພວກເຮົາສາມາດສ້າງລາຍຊື່ທີ່ເຊື່ອມໂຍງຂອງພວກເຮົາ. ໃນໂປແກຼມຂອງພວກເຮົາ, ພວກເຮົາສ້າງສອງລາຍຊື່ທີ່ບໍ່ມີສາຍເຊື່ອມໂຍງ. ຫລັງຈາກນັ້ນ, ພວກເຮົາຈັດຮຽງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງທັງສອງໂດຍການໃຊ້ວິທີການຈັດລຽງຂອງພວກເຮົາແລະຫຼັງຈາກນັ້ນພວກເຮົາສ້າງ ໜ້າ ທີ່ຂອງພວກເຮົາເພື່ອໃຫ້ໄດ້ສະຫະພາບແລະຈຸດເຊື່ອມໂຍງຂອງລາຍຊື່ທີ່ເຊື່ອມໂຍງຂອງພວກເຮົາ. ຫຼັງຈາກຈັດຮຽງທັງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງແລ້ວມັນງ່າຍທີ່ຈະສະແກນພວກມັນເປັນເສັ້ນທີ່ພວກເຮົາສາມາດມີສະຫະພາບແລະຈຸດເຊື່ອມຕໍ່ຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງຂອງພວກເຮົາ.

ຍົກຕົວຢ່າງ, ສ້າງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງກັນ 'list1' ແລະ 'list2', ແລະໃສ່ອົງປະກອບທັງສອງຂອງມັນໂດຍຊັ້ນ Node ຂອງພວກເຮົາໃນ java ຫຼື Node ໂຄງສ້າງໃນ c ++. ຫລັງຈາກນັ້ນ, ພວກເຮົາພົບສະຫະພັນຂອງທັງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງຂອງພວກເຮົາ list1 ແລະ list2 ໂດຍການ ນຳ ໃຊ້ຟັງຊັນທີ່ພວກເຮົາໄດ້ເຮັດ 'get_union' ເຊິ່ງພວກເຮົາເອົາຫົວ ໜ້າ ຂອງບັນຊີທີ່ເຊື່ອມໂຍງທັງສອງມາເປັນຂໍ້ໂຕ້ຖຽງໃນມັນແລະພວກເຮົາສ້າງລາຍຊື່ຊົ່ວຄາວເພື່ອຊ່ວຍປະຢັດສະຫະພັນ ອົງປະກອບທີ່ຢູ່ໃນບັນຊີຂອງທັງສອງລາຍການໂດຍການຊ່ວຍເຫຼືອຂອງ ໃນຂະນະທີ່ loop ທຳ ອິດໃນຂະນະທີ່ loop ເພື່ອໃສ່ສ່ວນຂອງລາຍຊື່ ທຳ ອິດໃນ temp. ບັນຊີລາຍຊື່ແລະທີສອງເພື່ອໃສ່ບັນຊີລາຍຊື່ 2 ອົງປະກອບໃນ temp. ບັນຊີລາຍຊື່ຖ້າພວກເຂົາບໍ່ຢູ່ໃນບັນຊີລາຍຊື່ແລະສຸດທ້າຍພວກເຮົາໄດ້ຮັບບັນຊີລາຍຊື່ທີ່ເຕັມໄປດ້ວຍບັນດາອົງປະກອບທີ່ມີຢູ່ທົ່ວໄປໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງທັງສອງ. ຫລັງຈາກນັ້ນ, ພວກເຮົາຈະ ນຳ ໃຊ້ວິທີການ 'Get Intersection' ຂອງພວກເຮົາເພື່ອຊອກຫາຈຸດຊ້ອນກັນຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງທັງສອງ, ໃນນັ້ນພວກເຮົາເອົາຫົວຂອງບັນຊີທັງສອງທີ່ເຊື່ອມໂຍງເຂົ້າມາແລະອີກເທື່ອ ໜຶ່ງ ພວກເຮົາຈະໃຊ້ ໃນຂະນະທີ່ loop ໃນມັນເພື່ອເພີ່ມສ່ວນປະກອບຂອງບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງທັງສອງເທົ່ານັ້ນຖ້າວ່າມັນມີຢູ່ທົ່ວໄປໃນບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງທັງສອງ.

ການປະຕິບັດ

ໂຄງການ C ++ ສຳ ລັບ Union ແລະ Intersection ຂອງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງ

#include<iostream>
#include<stdlib.h>
using namespace std;

struct Node
{
    int value;
    struct Node* next;
};

void insert(struct Node** head, int new_value)
{
    struct Node* NewNode = (struct Node*) malloc(sizeof(struct Node));

    NewNode->value = new_value;

    NewNode->next = (*head);

    (*head) = NewNode;
}

void Front_Back(struct Node* source, struct Node** front, struct Node** back)
{
    struct Node* fast;
    struct Node* slow;
    if (source==NULL || source->next==NULL)
    {
        *front = source;
        *back = NULL;
    }
    else
    {
        slow = source;
        fast = source->next;

        while (fast != NULL)
        {
            fast = fast->next;
            if (fast != NULL)
            {
                slow = slow->next;
                fast = fast->next;
            }
        }

        *front = source;
        *back = slow->next;
        slow->next = NULL;
    }
}

struct Node* Sort_merge(struct Node* fst, struct Node* sec)
{
    struct Node* result = NULL;

    if (fst == NULL)
        return(sec);
    else if (sec==NULL)
        return(fst);

    if (fst->value <= sec->value)
    {
        result = fst;
        result->next = Sort_merge(fst->next, sec);
    }
    else
    {
        result = sec;
        result->next = Sort_merge(fst, sec->next);
    }
    return(result);
}

void Sort(struct Node** head)
{
    struct Node *head_node= *head;
    struct Node *a, *b;

    if ((head_node == NULL) || (head_node->next == NULL))
        return;

    Front_Back(head_node, &a, &b);

    Sort(&a);
    Sort(&b);

    *head = Sort_merge(a, b);
}

struct Node *get_Union(struct Node *head1, struct Node *head2)
{
    struct Node *result = NULL;
    struct Node *t1 = head1, *t2 = head2;

    while (t1 != NULL && t2 != NULL)
    {
        if (t1->value < t2->value)
        {
            insert(&result, t1->value);
            t1 = t1->next;
        }

        else if (t1->value>t2->value)
        {
            insert(&result, t2->value);
            t2 = t2->next;
        }
        else
        {
            insert(&result, t2->value);
            t1 = t1->next;
            t2 = t2->next;
        }
    }

    while (t1 != NULL)
    {
        insert(&result, t1->value);
        t1 = t1->next;
    }
    while (t2 != NULL)
    {
        insert(&result, t2->value);
        t2 = t2->next;
    }

    return result;
}

struct Node *get_Intersection(struct Node *head1, struct Node *head2)
{
    struct Node *result = NULL;
    struct Node *t1 = head1, *t2 = head2;

    while (t1 != NULL && t2 != NULL)
    {
        if (t1->value < t2->value)
            t1 = t1->next;

        else if (t1->value > t2->value)
            t2 = t2->next;

        else
        {
            insert(&result, t2->value);

            t1 = t1->next;
            t2 = t2->next;
        }
    }

    return result;
}

void printList (struct Node *node)
{
    while (node != NULL)
    {
        cout<<node->value << " ";
        node = node->next;
    }
    cout<<endl;
}

int main()
{
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;
    struct Node* intersection_list = NULL;
    struct Node* union_list = NULL;

    insert(&head1, 20);
    insert(&head1, 4);
    insert(&head1, 15);
    insert(&head1, 10);
    insert(&head1, 11);

    insert(&head2, 10);
    insert(&head2, 2);
    insert(&head2, 4);
    insert(&head2, 8);

    Sort(&head1);
    Sort(&head2);

    intersection_list = get_Intersection(head1, head2);
    union_list = get_Union(head1, head2);

    cout<<"First list is \n";
    printList(head1);

    cout<<"\nSecond list is \n";
    printList(head2);

    cout<<"\nIntersection list is \n";
    printList(intersection_list);

    cout<<"\nUnion list is \n";
    printList(union_list);

    return 0;
}
First list is
4 10 11 15 20

Second list is
2 4 8 10

Intersection list is
10 4

Union list is
20 15 11 10 8 4 2

ໂປແກຼມ Java ສຳ ລັບ Union ແລະ Intersection ຂອງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງ

class Solution1
{
    Node head;


    class Node
    {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }


    void get_union(Node hd1, Node hd2)
    {
        Node t1 = hd1, t2 = hd2;


        while (t1 != null)
        {
            insert(t1.data);
            t1 = t1.next;
        }


        while (t2 != null)
        {
            if (!is_Present(head, t2.data))
                insert(t2.data);
            t2 = t2.next;
        }
    }

    void get_intrSection(Node hd1, Node hd2)
    {
        Node rst = null;
        Node t1 = hd1;


        while (t1 != null)
        {
            if (is_Present(hd2, t1.data))
                insert(t1.data);
            t1 = t1.next;
        }
    }


    void printList()
    {
        Node temp = head;
        while (temp != null)
        {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }


    void insert(int new_data)
    {

        Node new_node = new Node(new_data);


        new_node.next = head;


        head = new_node;
    }


    boolean is_Present(Node head, int data)
    {
        Node t = head;
        while (t != null)
        {
            if (t.data == data)
                return true;
            t = t.next;
        }
        return false;
    }


    public static void main(String args[])
    {
        Solution1 llist1 = new Solution1();
        Solution1 llist2 = new Solution1();
        Solution1 unin = new Solution1();
        Solution1 intersecn = new Solution1();


        llist1.insert(20);
        llist1.insert(4);
        llist1.insert(15);
        llist1.insert(10);


        llist2.insert(10);
        llist2.insert(2);
        llist2.insert(4);
        llist2.insert(8);

        intersecn.get_intrSection(llist1.head, llist2.head);
        unin.get_union(llist1.head, llist2.head);

        System.out.println("First List is");
        llist1.printList();

        System.out.println("Second List is");
        llist2.printList();

        System.out.println("Intersection List is");
        intersecn.printList();

        System.out.println("Union List is");
        unin.printList();
    }
}
First List is
10 15 4 20
Second List is
8 4 2 10
Intersection List is
4 10
Union List is
2 8 20 4 15 10

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບສະຫະພັນແລະການເຊື່ອມໂຍງຂອງສອງລາຍຊື່ທີ່ເຊື່ອມໂຍງ

ຄວາມສັບສົນເວລາ

 O (m + n) ບ່ອນທີ່ "m" ແລະ "n" ແມ່ນ ຈຳ ນວນຂອງສ່ວນປະກອບທີ່ມີໃນລາຍຊື່ ທຳ ອິດແລະອັນດັບສອງຕາມ ລຳ ດັບ.

ຄວາມສັບສົນໃນອະວະກາດ

 O (m + n) ບ່ອນທີ່ "m" ແລະ "n" ແມ່ນ ຈຳ ນວນຂອງສ່ວນປະກອບທີ່ມີໃນລາຍຊື່ ທຳ ອິດແລະອັນດັບສອງຕາມ ລຳ ດັບ.