Қосындысы берілген мәнге тең төрт сұрыпталған жиымнан төрт еселіктерді санаңыз


Күрделілік дәрежесі орта
Жиі кіреді Акколит Фанатика Moonfrog зертханалары Synopsys
Array Екілік іздеу Hash іздеу Сұрыптау

Проблемалық мәлімдеме

«Төрт сұрыпталған жиымнан қосындысы берілген х-ке тең болатын төртеуді санау» мәселесі сізге төрт бүтін жиым және х деп аталатын мән берілетіндігін айтады. Проблемалық есепте әрбір төртбұрыштың элементтерінің қосындысы берілген мәнге тең х-ге тең болатын қанша квадруплет құруға болатындығын сұрайды.

мысал

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

Түсініктеме: x = 5 мәнін беру үшін қорытынды жасай алатын 5 төртем бар.

 

Қосындысы х-ге тең төрт сұрыпталған жиымнан төртеу санау алгоритмі

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.

Түсіндіру

Біз бүтін төрт массив пен х санын бердік. Біздің міндетіміз - құруға болатын х-ге тең болатын төртемдердің жалпы санын табу. Ол үшін біз қолданамыз хэштеу. Біз а карта ол үшін, осылайша, бұл мәселені шешудің тиімді тәсілін ұсынады.

Санау мәнін 0-ге қойыңыз, бұл санау айнымалысы төрттіктердің санын сақтайды. Біз картаны жариялаймыз. Алғашқы екі жиымнан өтуді бастаңыз және алғашқы екі массивтің әр жұбының қосындысын кілт ретінде картаға сақтаңыз және картаның кілт мәні ретінде әрбір қосынды жиілігін қойыңыз. Егер қосындының ұқсас мәнінің тағы бір жұбын тапсақ. Біз тек қосынды жиілігінің мәнін көбейтеміз. Алғашқы екі массивтің толық өтуінен кейін бізде алғашқы екі массивтің жұптарының қосындысы болады.

Енді біз тағы екі массивті өтеміз, массивтен әр жұптың екі элементінің қосындысын аламыз. Бір жиымнан бір сан, екіншісінен бір сан. Сонда біз x-тің айырымы мен осы жұптың қосындысы картада бар-жоғын тексереміз. Сонда біз картадан сол жұптың жиілігін аламыз. Егер бар болса, біз санау жиілігін санауға осы жиілікті қосу арқылы арттырамыз, демек, біз барлық массивтерден бір төртбұрыш таптық. Себебі, егер бізде 10 + 20 = 30 болса, онда біз сондай мәндердің бірін таба аламыз, өйткені 30-10 дегеніміз осы шешімге ұқсас болып табылады және соңында санау мәнін қайтарамыз.

Қосындысы берілген мәнге тең төрт сұрыпталған жиымнан төрт еселіктерді санаңыз

код

С ++ коды, қосындысы берілген мәнге тең төрт сұрыпталған жиымнан төрттік санайды

#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 коды

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

Күрделілікті талдау

Уақыттың күрделілігі

O (n2қайда «N» - бұл массивтегі элементтер саны. Уақыттың N ^ 2 полиномдық күрделілігіне қол жеткіздік, өйткені әр массивтен элементтерді ғана өткіздік.

Ғарыштың күрделілігі

O (n2қайда «N» - бұл массивтегі элементтер саны. HashMap-да сақталатын элементтер саны екі массивтің элементтері болғандықтан. Біз кеңістіктің квадраттық күрделілігіне қол жеткіземіз.