Bir Dizidəki Müsbət Mənfi Dəyərlərin Cütlüyü

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Belzabar Honeywell Hulu Nvidia Robinlik Vəngilti
Geyim SükutBaxılıb 79

Cütlüyündə müsbət mənfi dəyərlər array Məsələ ayrı A tamlığı vermişiksə, massivdə mövcud olan bir ədədin müsbət və mənfi dəyərinə sahib olan bütün cütləri çap edin. Cütləri meydana çıxma sırasına görə çap etməliyik. Hər hansı bir elementi ilk olaraq görünən bir cüt əvvəlcə çap olunmalıdır.

misal

Input:

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

Çıxış:

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

Yanaşma 1: Kobud güc

Giriş massivindəki hər bir A [i] elementi üçün indeksin I-dən çox olan massivdə –A [i] nin olub olmadığını yoxlayın, sonra bu cütü yazdırır.

Alqoritm

  1. 0-dan n-1 aralığında I üçün bir döngə çalıştırın
    1. J üçün i + 1 - n-1 aralığında bir döngə çalıştırın
      1. A [i] -A [j] -ə bərabərdirsə, bu cütü çap edin.
    2. Qayıt.

Dizidəki Müsbət Mənfi Dəyərlərin Cütlüyünü tapmaq üçün C ++ proqramı

#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

Bir dizidəki Müsbət Mənfi Dəyərlər Cütlüyünü tapmaq üçün JAVA proqramı

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

Mürəkkəblik təhlili

Zaman mürəkkəbliyi

Hər ikisi də n ölçülü iki iç içə döngə istifadə edirik. Beləliklə, ümumi vaxt mürəkkəbliyi O (N ^ 2)

Kosmik mürəkkəblik

Məkan mürəkkəbliyi olduğu üçün əlavə yer istifadə etmirik O (1)

Yanaşma 2: Hashing istifadə

Əsas fikir

Dizidə hansı elementlərin olduğunu bir hash cədvəlində saxlaya bilərik. Artıq massivdəki hər bir A [i] elementi üçün hash cədvəlindəki –A [i] -in 1-ə bərabər olub olmadığını yoxlayın, əgər 1-dirsə, bu cütü və A [i] və –A azalma dəyərini çap edin. [i] hash cədvəlində 1 ilə, eyni cütü iki dəfə çap etməyimiz üçün.

Alqoritm

  1. Bir hash cədvəlini başladın.
  2. Hər elementin tezliyini hash cədvəlində saxlayın.
  3. 0-dan n-1 aralığında I üçün bir döngə çalıştırın
    1. –A [i] hash cədvəlində 1-ə bərabərdirsə, bu cütü yazdırın və A [i] və –A [i] dəyərini 1-ə endirin.

Nümunə ilə başa düş

A giriş massivini götürək [] = {2, 3, -1, -2, 9, 1}

Beləliklə hash masamız belə görünür:

Bir Dizidəki Müsbət Mənfi Dəyərlərin CütlüyüPin

İndi serialı təkrarlayacağıq,

Narıncı rəng indiki indeksi göstərir,

Bir Dizidəki Müsbət Mənfi Dəyərlərin CütlüyüPin Bir Dizidəki Müsbət Mənfi Dəyərlərin CütlüyüPin

Bir Dizidəki Müsbət Mənfi Dəyərlərin CütlüyüPin Pin Pin Pin

Beləliklə, son nəticə: -2 2 -1 1-dir

Dizidəki Müsbət Mənfi Dəyərlərin Cütlüyünü tapmaq üçün C ++ proqramı

#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

Bir dizidəki Müsbət Mənfi Dəyərlər Cütlüyünü tapmaq üçün JAVA proqramı

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

Mürəkkəblik təhlili

Zaman mürəkkəbliyi

Bütün massivi iki dəfə təkrarlayırıq, buna görə də zamanın mürəkkəbliyi O (N).

Kosmik mürəkkəblik

Bir hash masa istifadə edirik, beləliklə kosmik mürəkkəblikdir O (N).

References

Translate »