Пребройте четирикратно от четири сортирани масива, чиято сума е равна на дадена стойност x


Ниво на трудност M
Често задавани в Аколит Фанатиците Moonfrog Labs Synopsys
Array Двоично търсене Хашиш Търсене сортиране

Декларация за проблема

Проблемът „Преброяване на четворки от четири сортирани масива, чиято сума е равна на дадена стойност x“, посочва, че са ви дадени четири целочислени масива и стойност, наречена x. Изложението на проблема иска да открие колко четворки могат да се образуват, от които сумата от елементи на всеки четворка може да има добавяне, равно на дадената стойност, наречена x.

Пример

int arr1[] = { 2, 5, 6, 9 };

int arr2[] = { 1, 3, 7, 11 };

int arr3[] = { 1, 5, 6, 8 };

int arr4[] = { 2, 3, 5, 10 };

Sum=32
5

Обяснение: Има 5 четворки, които могат да сумират, за да дадат необходимата стойност x = 5.

 

Алгоритъм за броене на четворки от четири сортирани масива, чиято сума е x

1. Set the value of count to 0.
2. Declare a map.
3. Traverse the first and second list and store the sum of each pair that can be formed with the two lists into the map along with their frequency.
4, Traverse the other two arrays.
    1. Pick a sum of each pair from the two arrays and check if the x-sum is present in a map.
        1. If present then gets their frequency and add it to the value of count.
5. Return count.

Обяснение

Дадохме четири масива от цели числа и число x. Нашата задача е да намерим общия брой четворки, които могат да се образуват, който е равен на х. За това ще използваме хеширане. Ще използваме карта за това по този начин ще осигури ефективен подход за решаване на този въпрос.

Задайте стойността на count на 0, тази променлива на count ще съхранява броя на четворките. Ще декларираме карта. Започнете да обхождате първите два масива и съхранявайте сумата от всяка двойка от първите два масива в картата като ключ и поставете честотата на всяка сума като стойност на ключ в картата. Ако намерим друга двойка с подобна стойност на сумата. Просто увеличаваме стойността на честотата на сумата. След пълното обхождане на първите два масива имаме сбор от двойки от първите два масива.

Сега ще преминем към още два обхода на масиви, ще вземем сумата от два елемента от всяка двойка от масив. Едно число от един масив и едно число от друг. След това ще проверим дали разликата от x и сумата от тази двойка присъства в карта. Тогава ще получим честотата на тази двойка от картата. Ако присъства, ще увеличим стойността на count чрез добавяне на тази честота към броя, което означава, че сме намерили един четворка от всички масиви. Това е така, защото ако имаме 10 + 20 = 30, тогава можем също да намерим една от стойностите, тъй като 30-10 е какво, подобно се случва с това решение и накрая ще върнем стойността на count.

Пребройте четирикратно от четири сортирани масива, чиято сума е равна на дадена стойност x

код

C ++ код за броене на четворки от четири сортирани масива, чиято сума е равна на дадена стойност x

#include <iostream>
#include<unordered_map>

using namespace std;

int getNumberOfQuadruples(int arr1[], int arr2[], int arr3[],int arr4[], int n, int x)
{
    int count = 0;

    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            MAP [arr1[i] + arr2[j]]++;

    for (int k = 0; k < n; k++)
        for (int l = 0; l < n; l++)
        {
            int p_sum = arr3[k] + arr4[l];

            if (MAP.find(x - p_sum) != MAP.end())
                count += MAP [x - p_sum];
        }

    return count;
}
int main()
{
    int arr1[] = { 2, 5, 6, 9 };
    int arr2[] = { 1, 3, 7, 11 };
    int arr3[] = { 1, 5, 6, 8 };
    int arr4[] = { 2, 3, 5, 10 };

    int n = sizeof(arr1) / sizeof(arr1[0]);
    int x = 32;
    cout << "Count = "<< getNumberOfQuadruples (arr1, arr2, arr3, arr4, n, x);
    return 0;
}
Count = 3

Java код за броене на четворки от четири сортирани масива, чиято сума е равна на дадена стойност x

import java.util.HashMap;

class QuadrupletsSum
{
    public static int getNumberOfQuadruples (int arr1[], int arr2[], int arr3[], int arr4[], int n, int x)
    {
        int count = 0;

        HashMap<Integer,Integer> MAP = new HashMap<>();

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if(MAP.containsKey(arr1[i] + arr2[j]))
                    MAP.put((arr1[i] + arr2[j]), MAP.get((arr1[i] + arr2[j]))+1);
                else
                    MAP.put((arr1[i] + arr2[j]), 1);

        for (int k = 0; k < n; k++)
            for (int l = 0; l < n; l++)
            {
                int p_sum = arr3[k] + arr4[l];

                if (MAP.containsKey(x - p_sum))
                    count += MAP.get(x - p_sum);
            }

        return count;
    }
    public static void main(String[] args)
    {
        int arr1[] = { 2, 5, 6, 9 };
        int arr2[] = { 1, 3, 7, 11 };
        int arr3[] = { 1, 5, 6, 8 };
        int arr4[] = { 2, 3, 5, 10 };

        int n = arr1.length;
        int x = 32;
        System.out.println("Count = "
                           + getNumberOfQuadruples (arr1, arr2, arr3, arr4, n, x));
    }
}
Count = 3

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

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

На2където "н" е броят на елементите в масива. Постигнахме полиномна времева сложност на N ^ 2, защото всеки път обхождахме само елементите от два масива.

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

На2където "н" е броят на елементите в масива. Тъй като броят на елементите, които се съхраняват в HashMap, ще бъдат елементите от два масива. Постигаме квадратична космическа сложност.