Пар позитивних негативних вредности у низу


Ниво тешкоће Лако
Често питани у амазонка Белзабар Хонеивелл Хулу Нвидиа робинхоод Заштектати
Ред Хасх

У пару позитивних негативних вредности у ан поредак проблем дали смо низ А различитих целих бројева, исписати све парове који имају позитивну и негативну вредност броја који постоји у низу. Морамо исписати парове по редоследу њиховог појављивања. Прво треба одштампати пар чији се било који елемент појави први.

Пример

Улаз:

A[]={2, 3, -1, -2, 9, 1}

Излаз:

Pairs having positive value and negative in the array are: -2 2 -1 1

Приступ 1: Груба сила

За сваки елемент А [и] у улазном низу, проверите да ли је –А [и] присутан у низу са индексом већим од И ако је присутан, а затим исписује овај пар.

Алгоритам

  1. Покрените петљу за И у опсегу од 0 до н-1
    1. Покрените петљу за ј у опсегу и + 1 до н-1
      1. Ако је А [и] једнако -А [ј], одштампајте овај пар.
    2. Повратак.

Ц ++ програм за проналажење пара позитивних негативних вредности у низу

#include <bits/stdc++.h>
using namespace std;
void printPairs(vector<int> &A)
{
    int n = A.size();
    cout << "Pairs having positive value and negative in the array are: ";
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (A[i] == -A[j])
            {
                if (A[i] <= 0)
                {
                    cout << A[i] << " " << (-A[i]) << " ";
                }
                else
                {
                    cout << (-A[i]) << " " << A[i] << " ";
                }
            }
        }
    }
    cout << endl;
    return;
}
int main()
{
    vector<int> A = {2, 3, -1, -2, 9, 1};
    printPairs(A);
    return 0;
}
Pairs having positive value and negative in the array are: -2 2 -1 1

ЈАВА програм за проналажење пара позитивних негативних вредности у низу

public class Main
{
    static void printPairs(int[] A)
    {
        int n = A.length;
        System.out.print("Pairs having positive value and negative in the array are: ");
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (A[i] == -A[j])
                {
                    if (A[i] <= 0)
                    {
                       A[i]=-A[i];
                    }
                    System.out.print(A[i]+" -"+A[i]+" ");
                }
            }
        }
        return;
    }
  public static void main(String[] args) {
    int[] A={2, 3, -1, -2, 9, 1};
    printPairs(A);
  }
}
Pairs having positive value and negative in the array are: 2 -2 1 -1

Анализа сложености

Временска сложеност

Користимо две угнежђене петље, обе величине н. Дакле, укупна временска сложеност је О (Н ^ 2)

Свемирска сложеност

Не користимо никакав додатни простор, па је сложеност простора О (1)

Приступ 2: Коришћење хеширања

Главна идеја

У хеш табели можемо да сачувамо који су елементи присутни у низу. Сада за сваки елемент А [и] у низу проверите да ли –А [и] у хеш табели има вредност 1 или не, ако је 1 онда испишите овај пар и умањите вредност А [и] и –А [и] у хеш табели за 1, тако да нећемо исписати исти пар два пута.

Алгоритам

  1. Иницијализујте хеш табелу.
  2. Похраните учесталост сваког елемента у хеш табелу.
  3. Покрените петљу за И у опсегу од 0 до н-1
    1. Ако –А [и] има вредност 1 у хеш таблици, одштампајте овај пар и вредност А [и] и –А [и] умањите за 1.

Разумети на примеру

Узмимо улазни низ А [] = {2, 3, -1, -2, 9, 1}

Дакле, наша хеш табела изгледамо овако:

Пар позитивних негативних вредности у низу

Сада ћемо поновити низ,

Наранџаста боја показује тренутни индекс,

Пар позитивних негативних вредности у низу Пар позитивних негативних вредности у низу

Пар позитивних негативних вредности у низу

Дакле, коначни резултат је: -2 2 -1 1

Ц ++ програм за проналажење пара позитивних негативних вредности у низу

#include <bits/stdc++.h>
using namespace std;
void printPairs(vector<int> &A)
{
    int n = A.size();
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    cout << "Pairs having positive value and negative in the array are: ";
    for (int i = 0; i < n; i++)
    {
        if (hash_table[-A[i]] == 1)
        {
            if (A[i] <= 0)
            {
                cout << A[i] << " " << (-A[i]) << " ";
            }
            else
            {
                cout << (-A[i]) << " " << A[i] << " ";
            }
            hash_table[A[i]]--;
            hash_table[-A[i]]--;
        }
    }
    cout << endl;
    return;
}
int main()
{
    vector<int> A = {2, 3, -1, -2, 9, 1};
    printPairs(A);
    return 0;
}
Pairs having positive value and negative in the array are: -2 2 -1 1

ЈАВА програм за проналажење пара позитивних негативних вредности у низу

import java.util.*; 
public class Main
{
    static void printPairs(int[] A)
    {
        int n = A.length;
        HashMap<Integer,Integer> hash_table = new HashMap<Integer,Integer>();
        for (int i = 0; i < n; i++)
        {
            hash_table.put(A[i],1);
        }
        System.out.print("Pairs having positive value and negative in the array are: ");
        for (int i = 0; i < n; i++)
        {
            if(hash_table.containsKey(-1*A[i]) && hash_table.get(-1*A[i])==1)
            {
                if (A[i] <= 0)
                {
                    A[i]*=-1;
                }
                System.out.print(A[i]+" -"+A[i]+" ");
                hash_table.put(A[i],0);
                hash_table.put(-1*A[i],0);
            }
        }
        return;
    }
  public static void main(String[] args) {
    int[] A={2, 3, -1, -2, 9, 1};
    printPairs(A);
  }
}
Pairs having positive value and negative in the array are: -2 2 -1 1

Анализа сложености

Временска сложеност

Два пута понављамо читав низ, тако да је временска сложеност НА).

Свемирска сложеност

Користимо хеш таблицу, тако да је сложеност простора НА).

Референце