Нийлбэр нь өгөгдсөн x-тэй тэнцүү дөрвөн эрэмбэлэгдсэн массиваас дөрвөлжийг тоол  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Accolite Фанатикууд Moonfrog лабораторууд Синопсис
Array Хоёртын хайлт Хаш хайх Ангилах

Асуудлын мэдэгдэл  

"Нийлбэр нь өгөгдсөн 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

Тайлбар: Шаардлагатай x = 5 утгыг гаргахын тулд 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 тоог өгсөн. Бидний даалгавар бол х-тэй тэнцүү нийт дөрвөн ихэр хүүхдийн тоог олох явдал юм. Үүний тулд бид ашиглах болно хэшээл. Бид a-г ашиглах болно газрын зураг Үүний тулд энэ асуултыг шийдвэрлэх үр дүнтэй арга замыг бий болгох болно.

мөн үзнэ үү
График ба түүний дүрслэл

Тооны утгыг 0 болгож, энэ тооллогын хувьсагч нь дөрвөн ихрийн тоог хадгалах болно. Бид газрын зургийг зарлах болно. Эхний хоёр массивыг дайрч эхэлж, эхний хоёр массивын хос бүрийн нийлбэрийг газрын зураг дээр түлхүүр болгон хадгалж, нийлбэр бүрийн давтамжийг түлхүүрийн утга болгон газрын зурагт оруулна. Хэрэв бид нийлбэрийн ижил утгатай өөр нэг хосыг олвол. Бид нийлбэр давтамжийн утгыг л нэмэгдүүлдэг. Эхний хоёр массивыг бүрэн туулсны дараа бид эхний хоёр массиваас хосуудын нийлбэртэй болно.

Одоо бид өөр хоёр массивыг туулах болно, бид массиваас хос бүрийн хоёр элементийн нийлбэрийг авна. Нэг массиваас нэг тоо, нөгөө массиваас нэг тоо. Дараа нь бид x-ийн ялгаа ба энэ хосын нийлбэрийг газрын зураг дээр байгаа эсэхийг шалгана. Дараа нь бид газрын зураг дээрээс тухайн хосын давтамжийг авах болно. Хэрэв одоо байгаа бол тооллогод энэ давтамжийг нэмж тоолох утгыг нэмэгдүүлэх болно, энэ нь бүх массиваас нэг дөрвөлсөн тоог олсон гэсэн үг юм. Учир нь бид 10 + 20 = 30-тэй бол 30-10 нь энэ шийдэлтэй ижил төстэй зүйл болж байгаа тул тооллын утгыг буцааж өгөх болно.

Нийлбэр нь өгөгдсөн x-тэй тэнцүү дөрвөн эрэмбэлэгдсэн массиваас дөрвөлжийг тоолPin

код  

Нийлбэр нь өгөгдсөн x-тэй тэнцүү дөрвөн эрэмбэлэгдсэн массиваас дөрвөлж тоолох C ++ код

#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

Нийлбэр нь өгөгдсөн x-тэй тэнцүү дөрвөн эрэмбэлэгдсэн массиваас дөрөв дахин тоолох 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-д хадгалагдах элементийн тоо нь хоёр массивын элемент байх тул. Бид квадрат орон зайн нарийн төвөгтэй байдалд хүрдэг.