Підрахуйте вчетверо з чотирьох відсортованих масивів, сума яких дорівнює заданому значенню x


Рівень складності Medium
Часто запитують у Accolite Фанатики Moonfrog Labs Синопсис
масив Двійковий пошук Мішанина Пошук Сортування

Постановка проблеми

Проблема “Підрахувати вчетверо з чотирьох відсортованих масивів, сума яких дорівнює заданому значенню 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. Наше завдання - знайти загальну кількість четвертих, які можна сформувати, що дорівнює x. Для цього ми будемо використовувати хешування. Ми будемо використовувати карта для цього таким чином він забезпечить ефективний підхід до вирішення цього питання.

Встановіть значення count на 0, ця змінна count буде зберігати кількість четвірок. Ми оголосимо карту. Почніть обхід перших двох масивів і збережіть суму кожної пари перших двох масивів на карті як ключ і поставте на карту частоту кожної суми як значення ключа. Якщо ми знайдемо ще одну пару подібного значення суми. Ми просто збільшуємо значення частоти суми. Після повного обходу перших двох масивів ми маємо суму пар з перших двох масивів.

Тепер ми підемо на ще два обходи масивів, ми підберемо суму двох елементів кожної пари з масиву. Одне число з одного масиву і одне число з іншого. Тоді ми перевіримо, чи на карті присутня різниця х та суми цієї пари. Тоді ми отримаємо з карти частоту цієї пари. Якщо він присутній, ми будемо збільшувати значення count, додаючи цю частоту до count, що означає, що ми знайшли одну четверку з усіх масивів. Це тому, що якщо ми маємо 10 + 20 = 30, то ми також можемо знайти одне зі значень, оскільки 30-10 - це те, що відбувається подібно до цього рішення, і нарешті, ми повернемо значення count.

Підрахуйте вчетверо з чотирьох відсортованих масивів, сума яких дорівнює заданому значенню x

код

Код С ++ для підрахунку четвірок з чотирьох відсортованих масивів, сума яких дорівнює заданому значенню 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" - кількість елементів у масиві. Ми досягли поліноміальної часової складності N ^ 2, оскільки кожен раз обходили лише елементи з двох масивів.

Складність простору

О (н.)2де "N" - кількість елементів у масиві. Оскільки кількість елементів, що зберігаються в HashMap, буде елементами з двох масивів. Ми досягаємо квадратної складності простору.