З улікам двух сартаваных масіваў знайсці ўсе пары, сума якіх роўная х


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка facebook
масіў гашыш хэшавання

Пастаноўка праблемы

Даецца два несартаваныя масівы, знайсці ўсе пары, сума якіх роўная х, праблема сцвярджае, што вам дадзены два масівы цэлых лікаў, якія не сартаваны, і значэнне, якое называецца sum. Пастаноўка задачы патрабуе высветліць агульную колькасць пар і раздрукаваць усе тыя пары, якія складаюцца з зададзеным значэннем, якое называецца сума.

Прыклад

arr1[] = { 3,6,1,4,8,2}

arr2[] = { 2,1,5,7,2,4}

sum = 9
(8, 1), (4, 5) (2, 7)

Тлумачэнне: Усе тры пары маюць лік, сума якога роўная зададзенаму значэнню 9.

arr1[] = { 2,5,1,7,9}

arr2[] = { 3,6,8,1,0}

sum = 7
(1, 6), (7, 0)

Тлумачэнне: Абедзве дзве пары маюць лік, сума якога роўная дадзенаму значэнню 7.

Алгарытм пошуку ўсіх пар, якія маюць суму = х, у двух несартаваных масівах

1. Declare a Set.
2. Insert all the values of array1 into the Set.
3. Traverse the array2.
4. Check if the difference of sum and each number of array2 is present in a set.
5. If present then prints the difference and the current array element.

Тлумачэнне

З улікам двух сартаваных масіваў знайдзіце ўсе пары, сума якіх роўная х. Для гэтага мы будзем выкарыстоўваць набор. Набор таксама забяспечвае магчымасць выдалення агульных элементаў. Што мы збіраемся зрабіць, гэта ўставіць усе значэнні array1 у набор. Тут, калі набор выдаляе альбо не выдаляе элементы. Нас гэта не хвалюе, бо нам патрэбны толькі нумар, каб праверыць, ці можна сфармаваць пару.

Пры праходжанні першага масіва мы ўстаўляем усе яго значэнні ў набор. Пазней, з дапамогай гэтага набору, мы знойдзем, ці маем якую-небудзь пару, якую можна ўтварыць, сума якой роўная дадзенаму значэнню, якое называецца сума. Калі мы скончылі з устаўкай усіх значэнняў у набор, мы пройдзем масіў 2.

Пачынаючы з першага элемента другога масіва, мы будзем правяраць розніцу зададзенага значэння і кожнага значэння другога масіва падчас праходжання. Падобная рэч, бо мы можам дадаць два лікі, кажуць a + b = c, і цяпер, калі ў нас ёсць толькі b і c, з дапамогай cb мы можам даведацца пра "a". Тое ж самае тут, у нас ёсць выніковае значэнне, якое мы можам даведацца, якое значэнне патрабуецца для запаўнення пары. Вось чаму мы шукаем розніцу ў суме і кожнаму значэнню array2 у array1. Калі мы знойдзем пары проста раздрукуюць розніцу пары і бягучага элемента масіва, гэта будзе неабходная пара.

З улікам двух сартаваных масіваў знайдзіце ўсе пары, сума якіх роўная х

код

Код C ++, каб знайсці ўсе пары, якія маюць sum = x, у двух несартаваных масівах

#include<iostream>
#include<unordered_set>

using namespace std;

void getPairsofSum(int arr1[], int arr2[], int l1, int l2, int sum)
{
    unordered_set<int> MAP;
    for (int i = 0; i < l1; i++)
        MAP.insert(arr1[i]);

    for (int j = 0; j < l2; j++)
        if (MAP.find(sum - arr2[j]) != MAP.end())
            cout << sum - arr2[j] << " "<< arr2[j] << endl;
}
int main()
{
    int arr1[] = { 3,6,1,4,8,2};
    int arr2[] = { 2,1,5,7,2,4};
    int sum = 9;
    int l1 = sizeof(arr1) / sizeof(int);
    int l2 = sizeof(arr2) / sizeof(int);
    getPairsofSum(arr1, arr2, l1, l2, sum);
    return 0;
}
8 1
4 5
2 7

 

Код Java, каб знайсці ўсе пары, якія маюць sum = x, у двух несартаваных масівах

import java.util.HashMap;

class PairofSumUnsortedArray
{
    public static void getPairsofSum(int arr1[], int arr2[], int l1, int l2, int sum)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        for (int i = 0; i < l1; i++)
            MAP.put(arr1[i], 0);

        for (int j = 0; j < l2; j++)
            if (MAP.containsKey(sum - arr2[j]))
                System.out.println(sum - arr2[j] + " " + arr2[j]);
    }
    public static void main(String[] args)
    {
        int arr1[] = { 3,6,1,4,8,2};
        int arr2[] = { 2,1,5,7,2,4};
        int sum = 9;
        getPairsofSum(arr1, arr2, arr1.length, arr2.length, sum);
    }
}
8 1
4 5
2 7

 

Аналіз складанасці

Часовая складанасць

O (макс. (П, м)) дзе "П" і «М» - даўжыня першага і другога масіва.

Касмічная складанасць

O (макс. (П, м)) дзе "П" і «М» - даўжыня першага і другога масіва.