دو منسلک فہرستوں میں سے جوڑے گنیں جن کی رقم ایک دی گئی قیمت کے برابر ہے


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایڈوب ایمیزون اوالارا Expedia فانٹکس گوگل بے شک مائیکروسافٹ پے پال Tesla
ہیکنگ لنکڈ لسٹ چھانٹ

مسئلہ یہ بیان

مسئلہ "دو منسلک فہرستوں میں سے جوڑیوں کی گنتی کرو جس کی رقم ایک دی گئی قیمت کے برابر ہے" اس حالت میں کہ آپ کو دو لنکڈ لسٹیں اور ایک انٹیجر ویلیو کا جوڑ دیا جائے مسئلہ بیان میں یہ جاننے کے لئے کہا گیا ہے کہ کتنی کل جوڑی کی دی گئی قیمت کے برابر رقم ہے۔

مثال کے طور پر

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 ++ میں ، ہم نے حل حل کرنے کے ل a منسلک فہرست کو نافذ کرنے کے لئے بیرونی طور پر ایک طریقہ تشکیل دیا ہے۔ لیکن جاوا میں ، ہمارے پاس لنکٹ لسٹ کی ایک اندرونی ساختہ کلاس ہے جس کی مدد سے ہم آسانی سے تمام انٹیجر اقدار کو منسلک فہرست میں ڈال سکتے ہیں۔ اب ہم نے دونوں سے منسلک فہرستوں میں جوڑی تلاش کرنے کے لئے کہا ہے جس کی تعداد دی گئی قیمت کے مطابق ہے۔

ہم تمام عددی اقدار کو منسلک فہرست میں ڈالنے جارہے ہیں۔ ہم استعمال کرنے جا رہے ہیں سیٹ کریں ڈیٹا سٹرکچر اور منسلک لسٹ 1 کی تمام اقدار کو عبور کرے گا اور ترتیب دینے کیلئے پہلی منسلک فہرست کی تمام اقدار کو محفوظ کرے گا۔ سیٹ ایک خصوصیت بھی فراہم کرتا ہے جو عام عناصر کو خود کار طریقے سے سیٹ سے ہٹ جاتا ہے۔ لہذا اگر ہم اگلی بار سیٹ کا استعمال کریں گے تو عام عناصر کو کوئی پریشانی نہیں ہوگی ، اور منسلک فہرست میں وہاں موجود کوئی بھی عام عنصر موجود نہیں ہوگا۔

اب ہمارے پاس سیٹ میں لنکڈ لسٹ 1 میں تمام ویلیوز ہیں۔ اب ہم دوسری منسلک فہرست کو عبور کریں گے اور چیک کریں گے کہ دوسری فہرست کی ایکس اور ہر قیمت کے درمیان فرق سیٹ میں موجود ہے یا نہیں۔ اگر موجود ہے تو ہم نے ابھی کے لئے ایک جوڑی ڈھونڈ لیا ہے اور اس کے ساتھ ہی ہم گنتی کی قدر میں بھی 1 اضافہ کریں گے۔ اس کا مطلب ہے کہ 1 جوڑی ملا اور یہ گنتی ہے۔ traversal کے آخر میں. گنتی کی قیمت جوڑی کی تعداد ہوگی جس کی قیمت دی گئی قدر کے برابر ہوگی۔

دو منسلک فہرستوں میں سے جوڑے گنیں جن کی رقم ایک دی گئی قیمت کے برابر ہے

ضابطے

C ++ دو منسلک فہرستوں میں سے جوڑے گننے کے ل to جس کی رقم دی گئی قیمت کے برابر ہے

#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) کہاں "این 1" اور "این 2" منسلک فہرست میں عناصر کی تعداد ہیں۔ ہم خطیر وقت کی پیچیدگی کو حاصل کرنے کے قابل ہیں۔ کیوں کہ ہم دونوں نے منسلک فہرستوں کو عبور کیا اور ہیش سیٹ کو استعمال کیا۔

خلائی پیچیدگی

چونکہ ہم نے دو منسلک فہرستوں میں ان پٹ اسٹور کیا اور ہیش سیٹ استعمال کیا۔ ہمارے پاس ایک خلا والی پیچیدگی کا حل ہے۔