配列内の正の負の値のペア


難易度 簡単に
よく聞かれる Amazon (アマゾン) ベルザバール ハニーウェル Huluは Nvidiaの ロビンフッド 悲鳴
配列 ハッシュ

の正の負の値のペアで 配列 異なる整数の配列Aを指定した場合、配列に存在する数値の正の値と負の値を持つすべてのペアを出力します。 ペアを出現順に印刷する必要があります。 いずれかの要素が最初に表示されるペアを最初に印刷する必要があります。

入力:

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

出力:

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

アプローチ1:ブルートフォース

入力配列内のすべての要素A [i]について、–A [i]が配列内に存在するかどうかを確認し、存在する場合はIより大きいインデックスを使用して、このペアを出力します。

アルゴリズム

  1. 0からn-1の範囲でIのループを実行します
    1. i +1からn-1の範囲でjのループを実行します
      1. A [i]が-A [j]と等しい場合は、このペアを出力します。
    2. 戻ります。

配列内の正の負の値のペアを見つけるためのC ++プログラム

#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

配列内の正の負の値のペアを見つけるためのJAVAプログラム

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

複雑さの分析

時間の複雑さ

サイズnのXNUMXつのネストされたループを使用しています。 したがって、合計時間計算量は O(N ^ 2)

スペースの複雑さ

余分なスペースを使用していないため、スペースの複雑さは O(1)

アプローチ2:ハッシュを使用する

本旨

配列に存在する要素をハッシュテーブルに格納できます。 次に、配列内の各要素A [i]について、ハッシュテーブルの–A [i]の値が1であるかどうかを確認し、1の場合は、このペアを出力して、A [i]と–Aの値をデクリメントします。 [i]同じペアを1回出力しないように、ハッシュテーブルにXNUMXずつ入れます。

アルゴリズム

  1. ハッシュテーブルを初期化します。
  2. 各要素の頻度をハッシュテーブルに格納します。
  3. 0からn-1の範囲でIのループを実行します
    1. ハッシュテーブルで–A [i]の値が1の場合、このペアを出力し、A [i]と–A [i]の値を1デクリメントします。

例を挙げて理解する

入力配列A [] = {2、3、-1、-2、9、1}を取り上げましょう。

したがって、ハッシュテーブルは次のようになります。

配列内の正の負の値のペア

次に、配列を繰り返します。

オレンジ色は現在のインデックスを示し、

配列内の正の負の値のペア 配列内の正の負の値のペア

配列内の正の負の値のペア

したがって、最終的な出力は次のようになります。-2 -2 1

配列内の正の負の値のペアを見つけるためのC ++プログラム

#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

配列内の正の負の値のペアを見つけるためのJAVAプログラム

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

複雑さの分析

時間の複雑さ

配列全体をXNUMX回反復しているため、時間計算量は オン).

スペースの複雑さ

ハッシュテーブルを使用しているので、スペースの複雑さは オン).

リファレンス