ペアの配列が与えられた場合、その中のすべての対称ペアを見つけます


難易度 簡単に
よく聞かれる Amazon (アマゾン) キャップジェミニ Cisco 費用無料 ムーンフロッグラボ Opera ゾーメ
配列 ハッシュ

すべての対称ペアを検索–いくつかのペアが与えられます 配列。 その中の対称ペアを見つける必要があります。 対称ペアは、ペアで(a、b)と(c、d)があり、「b」が「c」に等しく、「a」が「d」に等しい場合、つまり(1 、2)は(2、1)の対称ペアです。

ペアの配列が与えられた場合、その中のすべての対称ペアを見つけます

{{11, 20},{30,40},{4,5},{5,4},{40,30}}
(4, 5) (30, 40)

すべての対称ペアを見つけるアルゴリズム

  1. 宣言する ハッシュマップ.
  2. 一方、 i <n (配列の長さ)
    1. 作成セッションプロセスで 最初の値 array [i] [0]および 秒値 arr [i] [1]に。
    2. secondValueの値がnullでないかどうか、およびsecondValueの値がfirstValueと等しいかどうかを確認します
    3. trueの場合、secondValueとfirstValueを出力します。
    4. それ以外の場合は、firstValueとsecondValueをハッシュマップに配置します。
  3. ループが存在するまで、aからdまでのプロセスを繰り返します。

説明

配列ペアを指定しました。その配列内にいくつかの対称ペアが存在します。 問題のステートメントは、配列に存在するすべての対称ペアを見つける必要があることを示しています。 XNUMXつのループを使用して、両方の配列をXNUMXつずつトラバースするだけです。 しかし、それは私たちにより多くの時間の複雑さを要し、私たちは効率的なコードを持つことができません。 次に、より良いアプローチを使用して、最初に特定の順序でそれらを並べ替えようとしますが、効率も必要です。 したがって、効率的なプログラムを取得するには、ハッシュを使用する必要があります。

ハッシュマップを使用して、最初にペアの最初の要素を 最初の値 ペアのXNUMX番目の要素を 秒値、ペアの両方の要素をキーと値として使用できます。 あるペアのキーを別のペアの値と比較し、同じペアの値を別のペアのキーと比較することにより、マップ内でそれを検索します。

ハッシュマップを使用して、ペアの配列を指定した場合の例を考えてみましょう。その中のすべての対称ペアを検索します。

arr={{1, 2},{30,40},{6,9},{2,1},{9,6}}

配列のペア値をfirstValueとsecondValueに格納してから、それをチェックします。

i = 0、

firstValue = arr [i] [0] //最初の要素をペアにする

secondValue = arr [i] [1] // 2番目の要素をペアにする

firstValue = 1、secondValue = 2

マップに値があり、条件がfalseであるかどうかを確認して、両方の値をマップに配置します。

マップ= [{1:2}]

i = 1、

firstValue = arr [i] [0] //最初の要素をペアにする

secondValue = arr [i] [1] // 2番目の要素をペアにする

firstValue = 30、secondValue = 40

マップに値があり、条件がfalseであるかどうかを確認して、両方の値をマップに配置します。

Map = [{1:2}、{30:40}]

i = 2、

firstValue = arr [i] [0] //最初の要素をペアにする

secondValue = arr [i] [1] // 2番目の要素をペアにする

firstValue = 6、secondValue = 9

マップに値があり、条件がfalseであるかどうかを確認して、両方の値をマップに配置します。

Map=[{1:2},{30:40},{6:9}]

i = 3、

firstValue = arr [i] [0] //最初の要素をペアにする

secondValue = arr [i] [1] // 2番目の要素をペアにする

firstValue = 2、secondValue = 1

マップに値が存在し、「1」として存在するかどうかを2で確認します。次に、secondValueの要素がfirstValueと等しく、この条件も満たすかどうかを確認します。

したがって、(1、2)を出力します

Map=[{1:2},{30:40},{6:9}]

i = 4、

firstValue = arr [i] [0] //最初の要素をペアにする

secondValue = arr [i] [1] // 2番目の要素をペアにする

firstValue = 9、secondValue = 6

マップに値が存在し、「6」として存在するかどうかを9で確認します。次に、secondValueの要素がfirstValueと等しく、この条件も満たすかどうかを確認します。

したがって、(1、2)、(6、9)を出力します

Map=[{1:2},{30:40},{6:9}]

コード

すべての対称ペアを見つけるためのC ++プログラム

#include<unordered_map>
#include<iostream>
using namespace std;
void getSymmetricPair(int arr[][2], int row)
{
    unordered_map<int, int> myMap;

    for (int i = 0; i < row; i++)
    {
        int firstValue = arr[i][0];
        int secondValue = arr[i][1];

        if (myMap.find(secondValue) != myMap.end() && myMap[secondValue] == firstValue)
        {
            cout << "(" << secondValue << ", " << firstValue << ")"<<" ";
        }
        else
        {
            myMap[firstValue] = secondValue;
        }
    }
}
int main()
{
    int arr[5][2]= {{11,20},{30,40},{4,5},{5,4},{40,30}};
    getSymmetricPair(arr, 5);
}
(4, 5) (30, 40)

すべての対称ペアを見つけるJavaプログラム

import java.util.HashMap;
class pairSymmetrics
{
    static void getSymmetricPair(int arr[][])
    {
        HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();

        for (int i = 0; i < arr.length; i++)
        {
            int firstValue = arr[i][0];
            int secondValue = arr[i][1];
            Integer val = hashmap.get(secondValue);

            if (val != null && val == firstValue)
            {
                System.out.print("(" + secondValue + ", " + firstValue + ")" + " ");
            }
            else
            {
                hashmap.put(firstValue, secondValue);
            }
        }
    }

    public static void main(String arg[])
    {
        int arr[][]= {{11,20},{30,40},{4,5},{5,4},{40,30}};
        getSymmetricPair(arr);

    }
}
(4, 5) (30, 40)

複雑さの分析

時間の複雑さ

O(N) where 「n」 配列内の要素の数です。 HashMapを使用したので、で挿入/削除/検索を実行できます。 O(1) 時間。

スペースの複雑さ

O(N) where 「n」 配列内の要素の数です。 マップに要素を保存したので。 空間の複雑さは線形です。

リファレンス