Броји парове са две повезане листе чији је збир једнак датој вредности  


Ниво тешкоће Средњи
Често питани у адобе амазонка Авалара Екпедиа Фанатици гоогле Заиста мицрософт ПаиПал Тесла
Хасхинг Повезана листа сортирање

Изјава о проблему  

Проблем „Бројање парова са две повезане листе чији је збир једнак датој вредности“ наводи да су вам додељене две повезане листе и целобројна сума вредности. Изјава о проблему тражила је да се открије колико укупно пара има збир једнак датој вредности.

Пример  

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.

Објашњење

Као улаз добијамо целобројне вредности. Дакле, све ћемо их гурнути на повезане листе. У Ц ++-у смо екстерно креирали метод за примену повезане листе за извођење овог решења. Али у јави имамо уграђену класу повезане листе помоћу које можемо лако да потиснемо све целобројне вредности у повезану листу. Сада смо тражили да откријемо пар на обе повезане листе чији број сабира до дате вредности.

Види такође
Пронађи највеће д у низу тако да је а + б + ц = д

Пребацићемо све целобројне вредности на повезану листу. Користићемо Сет Структура података и прећи ће све вредности повезане листе1 и сачувати све вредности прве повезане листе коју треба поставити. Сет такође пружа функцију да се заједнички елементи аутоматски уклањају из скупа. Дакле, ако следећи пут будемо користили скуп, неће бити проблема са заједничким елементима, а такође неће бити нити једног од заједничких елемената на повезаној листи.

Сада имамо све вредности на повезаном списку 1 у скупу. Сада ћемо прећи преко друге повезане листе и проверити да ли је разлика између к и сваке вредности друге листе присутна у скупу или не. Ако је присутан, за сада смо пронашли пар, а такође ћемо повећати вредност бројања за 1. То значи да је пронађен 1 пар и броји се. На крају преласка. Вредност бројања биће број пара који има збир једнак датој вредности.

Броји парове са две повезане листе чији је збир једнак датој вредности

код  

Ц ++ за бројање парова са две повезане листе чија је сума једнака датој вредности

#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

Анализа сложености  

Сложеност времена

О (н1 + н2) где „Н1“   „Н2“ су бројеви елемената на повезаној листи. У могућности смо да постигнемо линеарну временску сложеност. Зато што смо прешли преко повезаних листа и користили ХасхСет.

Види такође
Одштампајте све поднизове са 0 збиром

Сложеност простора

Будући да смо податке похранили на две повезане листе и користили ХасхСет. Имамо решење сложености линеарног простора.