دوه تړلي لیستونو څخه جوړه جوړه کړئ چې مجموعه د ورکړل شوي ارزښت سره مساوي ده


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ایڈوب ترلاسه کړئ Amazon اویلارا ايکسپيډيا انځورونه د ګوګل په حقیقت کی د Microsoft وی.دا تسلا
ځورول تړلي لیست ترتیب کول

ستونزه بیان

ستونزه "د دوه تړل شوي لیستونو څخه جوړه جوړه کړئ چې مجموعه د ورکړل شوي ارزښت سره مساوي" حالت بیانوي چې تاسو ته دوه لینک شوي لیستونه او د پیسو بشپړ ارزښت ورکول کیږي. د ستونزې بیان وغوښتل ترڅو ومومي چې څومره مجموعي جوړه د ورکړل شوي ارزښت سره مساوي اندازه لري.

بېلګه

LinkedList1 = 11 à 6 à 1 à 8

LinkedList2 = 5 à 3 à 1 à 9

Sum = 9
2

توضیحي: دوه جوړه شتون لري د بیلګې په توګه ، 6 ، 3 ، او 8 ، 1 چې ورکړل شوي ارزښت 9 ته ارزښت اندازه کوي.

 

د تړل شوي لیستونو څخه جوړې شمېرنې الګوریتم چې جمع یې د ورکړل شوي ارزښت سره مساوي دي

1. Push all the integer values to the two different linked lists.
2. Declare a set.
3. Set the count to 0.
4. Iterate over the first linked list and put all the values of it into the linked list1.
5. Iterate over the second linked list
    1. Check if the set contains the difference between the value of x and a current element of linked list2.
        1. If true then increase the value of count by 1.
6. Return count.

تشریح

موږ ته د اعداد په توګه عدد ارزښتونه ورکړل شوي دي. نو ، موږ به دا ټول په تړل شوي لیستونو کې واچوو. په C ++ کې ، موږ په بهر کې د دې حل د ترسره کولو لپاره د تړلي لیست پلي کولو لپاره میتود چمتو کړی دی. مګر په جاوا کې ، موږ د لینک شوي لیست دننه جوړ شوی ټولګی لرو د دې په مرسته چې موږ وکولی شو په اسانۍ سره د تړلو لیست کې ټول انټرز ارزښتونه وباسو. اوس موږ غوښتنه کړې چې په دواړه تړل شوي لیستونو کې جوړه ومومئ چې شمیره ورکړل شوي ارزښت ته رسي.

موږ به ټول عدد ارزښتونه وصل شوي لیست ته اړ کړو. موږ کارولو ته ځو ټاکل شوی د معلوماتو جوړښت او به د تړل شوي لیست 1 ټول ارزښتونه تعقیب کړي او د ترتیب کولو لپاره د لومړي لینک شوي لیست ټول ارزښتونه زیرمه کړي. سیټ یوه ب featureه هم وړاندې کوي چې عام عناصر په اوتومات ډول له سیټ څخه حذف کیږي. نو که موږ بل ځل موږ سیټ وکاروو نو د ګډو عناصرو لپاره به هیڅ ستونزه ونلري ، او همدارنګه په تړل شوي لیست کې به هلته کوم عام عنصر شتون ونلري.

اوس موږ سیټ ته په تړل شوي لیست 1 کې ټول ارزښتونه لرو. اوس موږ به دوهم تړل شوی لیست راوباسي او وګورو چې د ایکس او دوهم لیست هر ارزښت ترمنځ سیټ کې شتون شتون لري یا نه. که چیرې حاضر وي نو موږ د اوس لپاره یوه جوړه موندلې او هم به موږ د 1 لخوا د شمېرنې ارزښت لوړ کړو. پدې معنی چې 1 جوړه موندل شوې او دا شمیرل کیږي. د تراویژل په پای کې. د شمېرنې ارزښت به د جوړې شمیره وي چې ورکړل شوي ارزښت سره مساوي وي.

دوه تړلي لیستونو څخه جوړه جوړه کړئ چې مجموعه د ورکړل شوي ارزښت سره مساوي ده

کوډ

C ++ د دوه تړل شوي لیستونو څخه جوړه شمیرو لپاره چې مجموعه د ورکړل شوي ارزښت سره مساوي ده

#include<iostream>
#include<unordered_set>

using namespace std;

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

void implementLinkedList(struct Node** headReference, int newItem)
{
    struct Node* newNode =	(struct Node*) malloc(sizeof(struct Node));

    newNode->data = newItem;

    newNode->next = (*headReference);

    (*headReference) = newNode;
}
int getPairOfsum (struct Node* head1, struct Node* head2,int sum)
{
    int count = 0;

    unordered_set<int> SET;

    while (head1 != NULL)
    {
        SET.insert(head1->data);

        head1 = head1->next;
    }

    while (head2 != NULL)
    {
        if (SET.find(sum - head2->data) != SET.end())
            count++;

        head2 = head2->next;
    }
    return count;
}
int main()
{
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;

    implementLinkedList (&head1,11);
    implementLinkedList (&head1, 6);
    implementLinkedList (&head1, 1);
    implementLinkedList (&head1, 8);

    implementLinkedList (&head2, 5);
    implementLinkedList (&head2, 3);
    implementLinkedList (&head2, 1);
    implementLinkedList (&head2, 9);

    int sum = 9;

    cout << "Count = "<< getPairOfsum (head1, head2, sum);
    return 0;
}
Count = 2

د دوه تړل شوي لیستونو څخه جوړې شمېرنې لپاره جاوا کوډ چې پیسې د ورکړل شوي ارزښت سره مساوي دي

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;

class PairOfSumInLinkedList1
{
    public static int getPairOfsum(LinkedList<Integer> head1, LinkedList<Integer> head2, int sum)
    {
        int count = 0;

        HashSet<Integer> SET = new HashSet<Integer>();

        Iterator<Integer> itr1 = head1.iterator();
        while (itr1.hasNext())
        {
            SET.add(itr1.next());

        }

        Iterator<Integer> itr2 = head2.iterator();
        while (itr2.hasNext())
        {
            if (!(SET.add(sum - itr2.next())))
                count++;

        }
        return count;
    }
    public static void main(String[] args)
    {
        Integer arr1[] = {11, 6, 1, 8};
        Integer arr2[] = {5, 3, 1, 9};

        LinkedList<Integer> head1 = new LinkedList<>(Arrays.asList(arr1));

        LinkedList<Integer> head2 = new LinkedList<>(Arrays.asList(arr2));

        int x = 9;

        System.out.println("Count = " + getPairOfsum(head1, head2, x));
    }
}
Count = 2

د پیچلتیا تحلیل

د وخت پیچلتیا

O (n1 + n2) هلته "n1" او "n2" په تړلي لیست کې د عناصرو شمیر دي. موږ وړ وړ وخت پیچلتیا لاسته راوړو. ځکه چې موږ دواړه تړلي لیستونه تعقیب کړل او د هش سیټ کارولو.

د ځای پیچلتیا

له هغه ځایه چې موږ پیوستون په دوه تړل شوي لیستونو کې ذخیره کړی او د هشسیټ کارولو څخه یې کار اخیستی. موږ د خطي خطي پیچلتیا حل لرو.