Cəmi verilmiş dəyərə bərabər olan iki əlaqəli siyahıdan cütləri sayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon Avalara Expedia Fanatics google Həqiqətən microsoft PayPal Tesla
Hashing Bağlı siyahı çeşidləyiciBaxılıb 34

Problem bəyanat

Məsələ “Cəmi verilmiş dəyərə bərabər olan iki əlaqəli siyahıdan cütləri sayın” məsələsi, sizə iki əlaqəli siyahı və tam ədəd cəmi verildiyini bildirir. Problem ifadəsi verilmiş dəyərə bərabər olan cəmi cütlüyün cəminin nə olduğunu öyrənməsini istədi.

misal

LinkedList1 = 11 à 6 à 1 à 8

LinkedList2 = 5 à 3 à 1 à 9

Sum = 9
2

İzahat: Dəyəri verilmiş 6-a cəmləyən iki cüt, yəni 3, 8 və 1, 9 var.

 

Cəmi verilmiş dəyərə bərabər olan əlaqəli siyahılardan cütlərin sayılması alqoritmi

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.

Izahat

Giriş olaraq bizə tam ədəd dəyərləri verilir. Beləliklə, hamısını əlaqəli siyahılara sövq edəcəyik. C ++ dilində bu həlli həyata keçirmək üçün əlaqəli bir siyahı tətbiq etmək üçün bir metod yaratdıq. Ancaq java'da, bütün tam dəyərləri əlaqəli siyahıya asanlıqla sövq edə biləcəyimiz köməyi ilə daxili bir siyahı sinfi var. İndi hər iki əlaqəli siyahıda sayın verilmiş dəyərə çatdığı cütü tapmağı xahiş etdik.

Bütün tam dəyərləri əlaqəli siyahıya köçürəcəyik. İstifadə edəcəyik Set Məlumat quruluşu və əlaqəli list1-in bütün dəyərlərindən keçəcək və qurulacaq ilk əlaqəli siyahının bütün dəyərlərini saxlayacaq. Dəst eyni zamanda ümumi elementlərin dəstdən avtomatik silinməsi xüsusiyyətini də təmin edir. Beləliklə, növbəti dəfə dəsti istifadə etsək, ortaq elementlər üçün heç bir problem olmayacaq və əlaqəli siyahıda da ortaq elementlərdən heç biri olmayacaqdır.

İndi əlaqəli siyahı 1-dəki bütün dəyərləri dəstə daxil etdik. İndi ikinci əlaqəli siyahıdan keçəcəyik və x ilə ikinci siyahının hər bir dəyəri arasındakı fərqin çoxluqda olub olmadığını yoxlayacağıq. Əgər mövcuddursa, hələlik bir cüt tapmışıq və saymanın dəyərini 1 artıracağıq. Bu, 1 cüt tapılmış deməkdir və sayılır. Keçidin sonunda. Saymanın dəyəri cəmi verilmiş dəyərə bərabər olan cütün sayı olacaqdır.

Cəmi verilmiş dəyərə bərabər olan iki əlaqəli siyahıdan cütləri sayınPin

Kodu

C ++ cəmi verilmiş dəyərə bərabər olan iki əlaqəli siyahıdan cütləri saymaq üçün

#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

Cəmi verilmiş dəyərə bərabər olan iki əlaqəli siyahıdan cütləri saymaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n1 + n2) hara “N1” və “N2” əlaqəli siyahıdakı elementlərin nömrələridir. Xətti zaman mürəkkəbliyinə nail ola bilərik. Çünki həm əlaqəli siyahılardan keçdik, həm də HashSet istifadə etdik.

Kosmik Mürəkkəblik

Girişi iki əlaqəli siyahıda saxladığımız və HashSet istifadə etdiyimiz üçün. Doğrusal bir kosmik mürəkkəblik həllinə sahibik.

Translate »