Cəmi verilmiş x-a bərabər olan dörd sıralanmış massivdən dördqatları sayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Akkolit Fanatics Moonfrog Laboratoriyaları Sinopsis
Geyim İkili axtarış Sükut Axtarış çeşidləyiciBaxılıb 36

Problem bəyanat

Məsələ “Cəmi verilən bir x-a bərabər olan dörd sıralanmış massivdən dördlüyü sayın” problemi, sizə dörd ədəd tam sıra və x adlı bir dəyər verildiyini bildirir. Problem ifadəsi, hər dördbucağın elementlərinin cəminin verilən x-a verilən dəyərə bərabər bir əlavə ala biləcəyindən neçə dördbucaq yarana biləcəyini soruşur.

misal

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

İzahat: Lazımi x = 5 vermək üçün xülasə edə bilən 5 dörd uşaq var.

 

Cəmi x olan dörd sıralanmış massivdən dördlərin sayılması alqoritmi

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.

Izahat

Dörd ədəd ədəd və x rəqəmi verdik. Bizim vəzifəmiz, meydana gələ bilən x-a bərabər olan dörd nəfərin ümumi sayını tapmaqdır. Bunun üçün istifadə edəcəyik qarışdırma. A istifadə edəcəyik xəritə bunun üçün bu şəkildə bu sualı həll etmək üçün təsirli bir yanaşma təmin edəcəkdir.

Sayı dəyərini 0 olaraq təyin edin, bu say dəyişən dördbucaq sayını saxlayacaq. Bir xəritə elan edəcəyik. İlk iki massivdən keçməyə başlayın və ilk iki sıra cütlüyünün cəmini bir düymə olaraq xəritədə saxlayın və hər cəmin tezliyini xəritəyə düymənin dəyəri kimi qoyun. Cəmin oxşar dəyərindən başqa bir cüt tapsaq. Yalnız cəmin tezliyini artırırıq. İlk iki massivin tam keçidindən sonra ilk iki sıra arasındakı cüt cəmimiz var.

İndi başqa iki sıra keçidinə gedəcəyik, bir cütdən hər cütün iki elementinin cəmini götürəcəyik. Bir sıra bir rəqəm və digər bir sıra. Sonra x və bu cütün cəminin fərqinin xəritədə olub olmadığını yoxlayacağıq. Sonra həmin cütlüyün tezliyini xəritədən əldə edəcəyik. Əgər mövcuddursa, sayını həmin tezliyi əlavə edərək sayma dəyərini artıracağıq, yəni bütün massivlərdən bir dördqat tapdıq. Çünki, 10 + 20 = 30-a sahibiksə, onda 30-10-da bu həll ilə bənzər bir şey olduğu üçün dəyərlərdən birini də tapa bilərik və nəticədə sayma dəyərini qaytaracağıq.

Cəmi verilmiş x-a bərabər olan dörd sıralanmış massivdən dördqatları sayınPin

Kodu

C ++ kodu cəmi verilmiş bir x-a bərabər olan dörd sıralanmış massivdən dördlü saymaq üçün

#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

Cəmi verilən bir x-a bərabər olan dörd sıralanmış massivdən dördləri saymaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n)2hara "N" massivdəki elementlərin sayıdır. Hər dəfə iki massivdən yalnız elementləri keçdiyimiz üçün N ^ 2 polinom zaman mürəkkəbliyinə nail olduq.

Kosmik Mürəkkəblik

O (n)2hara "N" massivdəki elementlərin sayıdır. HashMap-də saxlanılan elementlərin sayı iki massivin elementləri olacağından. Kvadrat məkan mürəkkəbliyinə nail oluruq.

Translate »