Рубрики

Найти четыре элемента, которые суммируют с заданным значением | Установите 2 (O (n ^ 2Logn) решение)

Для данного массива целых чисел найдите любую комбинацию из четырех элементов в массиве, сумма которых равна заданному значению X.

Например, если задан массив {10, 2, 3, 4, 5, 9, 7, 8} и X = 23, ваша функция должна вывести «3 5 7 8» (3 + 5 + 7 + 8 = 23).

Мы обсуждали алгоритм O (n ^ 3) в предыдущем посте на эту тему. Задача может быть решена за O (n ^ 2Logn) времени с помощью вспомогательного пространства.

Спасибо за то, что предложили этот метод. Ниже приводится подробный процесс.

Пусть входной массив будет A [].

  • Создайте вспомогательный массив aux [] и сохраните сумму всех возможных пар в aux []. Размер aux [] будет n * (n-1) / 2, где n — это размер A [].
  • Сортировать вспомогательный массив aux [].
  • Теперь задача сводится к тому, чтобы найти два элемента в aux [] с суммой, равной X. Мы можем использовать метод 1 этого поста, чтобы эффективно найти два элемента. Следует отметить следующее важное замечание. Элемент aux [] представляет пару из A []. Выбирая два элемента из aux [], мы должны проверить, имеют ли два элемента общий элемент A []. Например, если сумма первого элемента A [1] и A [2], а второй элемент — сумма A [2] и A [4], то эти два элемента aux [] не представляют четыре различных элемента входной массив A [].

Ниже приведена реализация вышеуказанного подхода:

C ++

#include <bits/stdc++.h>

using namespace std;

  
// нужна следующая структура
// для хранения парных сумм в aux []

class pairSum 

    public:

    int first; // индекс (int A []) первого элемента в паре

    int sec; // индекс второго элемента в паре

    int sum; // сумма пары

}; 

  
// Нужна следующая функция
// для библиотечной функции qsort ()

int compare (const void *a, const void * b) 

    return ( (*(pairSum *)a).sum - (*(pairSum*)b).sum ); 

  
// Функция для проверки наличия двух заданных пар
// есть общий элемент или нет

bool noCommon(pairSum a, pairSum b) 

    if (a.first == b.first || a.first == b.sec || 

            a.sec == b.first || a.sec == b.sec) 

        return false

    return true

  

  
// Функция находит четыре элемента с заданной суммой X

void findFourElements (int arr[], int n, int X) 

    int i, j; 

  

    // Создать вспомогательный массив для хранения всех парных сумм

    int size = (n*(n-1))/2; 

    pairSum aux[size]; 

  

    / * Генерируем все возможные пары из A [] и сохраняем суммы

    всех возможных пар в aux [] * /

    int k = 0; 

    for (i = 0; i < n-1; i++) 

    

        for (j = i+1; j < n; j++) 

        

            aux[k].sum = arr[i] + arr[j]; 

            aux[k].first = i; 

            aux[k].sec = j; 

            k++; 

        

    

  

    // Сортировка массива aux [] с использованием библиотечной функции для сортировки

    qsort (aux, size, sizeof(aux[0]), compare); 

  

    // Теперь запускаем две индексные переменные из двух углов массива

    // и перемещаем их навстречу друг другу.

    i = 0; 

    j = size-1; 

    while (i < size && j >=0 ) 

    

        if ((aux[i].sum + aux[j].sum == X) && 

                    noCommon(aux[i], aux[j])) 

        

            cout << arr[aux[i].first] << ", " << 

                    arr[aux[i].sec] << ", " << 

                    arr[aux[j].first] << ", " << 

                    arr[aux[j].sec] << endl; 

            return

        

        else if (aux[i].sum + aux[j].sum < X) 

            i++; 

        else

            j--; 

    

  
// Код драйвера

int main() 

    int arr[] = {10, 20, 30, 40, 1, 2}; 

    int n = sizeof(arr) / sizeof(arr[0]); 

    int X = 91; 

    findFourElements (arr, n, X); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С
Ниже приведена реализация этого метода.

#include <stdio.h>
#include <stdlib.h>

  
// Следующая структура необходима для хранения парных сумм в aux []

struct pairSum

{

    int first; // индекс (int A []) первого элемента в паре

    int sec; // индекс второго элемента в паре

    int sum;  // сумма пары

};

  
// Следующая функция необходима для библиотечной функции qsort ()

int compare (const void *a, const void * b)

{

    return ( (*(pairSum *)a).sum - (*(pairSum*)b).sum );

}

  
// Функция для проверки, если две заданные пары имеют общий элемент или нет

bool noCommon(struct pairSum a, struct pairSum b)

{

    if (a.first == b.first || a.first == b.sec ||

            a.sec == b.first || a.sec == b.sec)

        return false;

    return true;

}

  

  
// Функция находит четыре элемента с заданной суммой X

void findFourElements (int arr[], int n, int X)

{

    int i, j;

  

    // Создать вспомогательный массив для хранения всех парных сумм

    int size = (n*(n-1))/2;

    struct pairSum aux[size];

  

    / * Генерируем все возможные пары из A [] и сохраняем суммы

       всех возможных пар в aux [] * /

    int k = 0;

    for (i = 0; i < n-1; i++)

    {

        for (j = i+1; j < n; j++)

        {

            aux[k].sum = arr[i] + arr[j];

            aux[k].first = i;

            aux[k].sec = j;

            k++;

        }

    }

  

    // Сортировка массива aux [] с использованием библиотечной функции для сортировки

    qsort (aux, size, sizeof(aux[0]), compare);

  

    // Теперь запускаем две индексные переменные из двух углов массива

    // и перемещаем их навстречу друг другу.

    i = 0;

    j = size-1;

    while (i < size && j >=0 )

    {

        if ((aux[i].sum + aux[j].sum == X) && noCommon(aux[i], aux[j]))

        {

            printf ("%d, %d, %d, %d\n", arr[aux[i].first], arr[aux[i].sec],

                                     arr[aux[j].first], arr[aux[j].sec]);

            return;

        }

        else if (aux[i].sum + aux[j].sum < X)

            i++;

        else

            j--;

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = {10, 20, 30, 40, 1, 2};

    int n = sizeof(arr) / sizeof(arr[0]);

    int X = 91;

    findFourElements (arr, n, X);

    return 0;

}


Выход:

20, 1, 30, 40

Обратите внимание, что приведенный выше код печатает только одну четверку. Если мы удалим оператор return и добавим операторы «i ++; j–; ”, затем он печатает одну и ту же четверку пять раз. Код может быть изменен для печати всех четверок только один раз. Это было сохранено таким образом, чтобы было проще.

Временная сложность: шаг 1 занимает O (n ^ 2) времени. Второй шаг — сортировка массива размера O (n ^ 2). Сортировка может быть выполнена за O (n ^ 2Logn) время с использованием сортировки слиянием или кучи или любого другого алгоритма O (nLogn). Третий шаг занимает O (n ^ 2) времени. Таким образом, общая сложность O (n ^ 2Logn) .

Вспомогательное пространство: O (n ^ 2). Большой размер вспомогательного массива может быть проблемой в этом методе.

Решение на основе хеширования: O (n 2 Logn)

  1. Хранить суммы всех пар в хеш-таблице
  2. Пройдите через все пары еще раз и найдите X — (текущая сумма пары) в хеш-таблице.
  3. Если найдена пара с необходимой суммой, убедитесь, что все элементы являются различными элементами массива, и элемент не рассматривается более одного раза.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

// Программа CPP на основе хеширования, чтобы найти, есть ли
// четыре элемента с заданной суммой.
#include <bits/stdc++.h>

using namespace std;

  
// Функция находит четыре элемента с заданной суммой X

void findFourElements (int arr[], int n, int X)

{

    // Сохраняем суммы всех пар в хеш-таблице

    unordered_map<int, pair<int, int>> mp;

    for (int i = 0; i < n-1; i++)

        for (int j = i+1; j < n; j++)

            mp[arr[i] + arr[j]] = {i, j};

  

    // Обход всех пар и поиск

    // для X - (текущая сумма пары).

    for (int i = 0; i < n-1; i++)

    {

        for (int j = i+1; j < n; j++)

        {

            int sum = arr[i] + arr[j];

  

            // Если X-сумма присутствует в хеш-таблице,

            if (mp.find(X - sum) != mp.end())

            {

  

                // Убедимся, что все элементы

                // отдельные элементы массива и элемент

                // не рассматривается более одного раза.

                pair<int, int> p = mp[X - sum];

                if (p.first != i && p.first != j &&

                        p.second != i && p.second != j)

                {

                    cout << arr[i] << ", " << arr[j] << ", "

                         << arr[p.first] << ", "

                         << arr[p.second];

                    return;

                }

            }

        }

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = {10, 20, 30, 40, 1, 2};

    int n = sizeof(arr) / sizeof(arr[0]);

    int X = 91;

    findFourElements(arr, n, X);

    return 0;

}

Джава

// основанная на хешировании Java-программа для поиска
// если есть четыре элемента с заданной суммой.

import java.util.HashMap;

class GFG

{

static class pair

    int first, second; 

    public pair(int first, int second) 

    

        this.first = first; 

        this.second = second; 

    

}

  
// Функция находит четыре элемента
// с заданной суммой X

static void findFourElements(int arr[], 

                             int n, int X)

{

    // Сохраняем суммы всех пар в хеш-таблице

    HashMap<Integer,        

            pair> mp = new HashMap<Integer,

                                   pair>();

    for (int i = 0; i < n - 1; i++)

        for (int j = i + 1; j < n; j++)

            mp.put(arr[i] + arr[j],

                    new pair(i, j));

  

    // Обход всех пар и поиск

    // для X - (текущая сумма пары).

    for (int i = 0; i < n - 1; i++)

    {

        for (int j = i + 1; j < n; j++)

        {

            int sum = arr[i] + arr[j];

  

            // Если X-сумма присутствует в хеш-таблице,

            if (mp.containsKey(X - sum))

            {

  

                // Убедимся, что все элементы

                // отдельные элементы массива и элемент

                // не рассматривается более одного раза.

                pair p = mp.get(X - sum);

                if (p.first != i && p.first != j &&

                    p.second != i && p.second != j)

                {

                    System.out.print(arr[i] + ", " + arr[j] + 

                                              ", " + arr[p.first] + 

                                              ", " + arr[p.second]);

                    return;

                }

            }

        }

    }

}

  
// Код драйвера

public static void main(String[] args) 

{

    int arr[] = {10, 20, 30, 40, 1, 2};

    int n = arr.length;

    int X = 91;

    findFourElements(arr, n, X);

}

  
// Этот код предоставлен Принчи Сингхом

C #

// основанная на хешировании программа C # для поиска
// если есть четыре элемента с заданной суммой.

using System;

using System.Collections.Generic;             

      

class GFG

{

public class pair

    public int first, second; 

    public pair(int first, int second) 

    

        this.first = first; 

        this.second = second; 

    

}

  
// Функция находит четыре элемента
// с заданной суммой X

static void findFourElements(int []arr, 

                             int n, int X)

{

    // Сохраняем суммы всех пар в хеш-таблице

    Dictionary<int,     

               pair> mp = new Dictionary<int,

                                         pair>();

    for (int i = 0; i < n - 1; i++)

        for (int j = i + 1; j < n; j++)

            if(mp.ContainsKey(arr[i] + arr[j]))

                mp[arr[i] + arr[j]] = new pair(i, j);

            else

                mp.Add(arr[i] + arr[j], new pair(i, j));

  

    // Обход всех пар и поиск

    // для X - (текущая сумма пары).

    for (int i = 0; i < n - 1; i++)

    {

        for (int j = i + 1; j < n; j++)

        {

            int sum = arr[i] + arr[j];

  

            // Если X-сумма присутствует в хеш-таблице,

            if (mp.ContainsKey(X - sum))

            {

  

                // Убедимся, что все элементы

                // отдельные элементы массива и элемент

                // не рассматривается более одного раза.

                pair p = mp[X - sum];

                if (p.first != i && p.first != j &&

                    p.second != i && p.second != j)

                {

                    Console.Write(arr[i] + ", " + arr[j] + 

                                           ", " + arr[p.first] + 

                                           ", " + arr[p.second]);

                    return;

                }

            }

        }

    }

}

  
// Код драйвера

public static void Main(String[] args) 

{

    int []arr = {10, 20, 30, 40, 1, 2};

    int n = arr.Length;

    int X = 91;

    findFourElements(arr, n, X);

}
}

  
// Этот код предоставлен 29AjayKumar

Выход :

20, 30, 40, 1

Пожалуйста, пишите комментарии, если вы обнаружите, что какой-либо из приведенных выше кодов / алгоритмов неверен, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

Найти четыре элемента, которые суммируют с заданным значением | Установите 2 (O (n ^ 2Logn) решение)

0.00 (0%) 0 votes