特定の行列のすべての行に共通の要素


難易度 ミディアム
よく聞かれる Amazon (アマゾン) Cisco DEショウ Opera SAPラボ Zohoの
配列 ハッシュ ハッシング マトリックス

問題文

「与えられた行列のすべての行の共通要素」問題は、M * Nの行列が与えられていると述べています。 問題ステートメントは、O(M * N)時間で、行列の各行にある特定の行列のすべての共通要素を見つけるように要求します。

arr[]={{12, 1, 4, 5, 9},

{3, 8, 0, 4, 1},

{2, 7, 4, 1, 5},

{6, 3, 1, 9, 4}}
1 4

説明:1と4は、特定のマトリックスの各行に存在するマトリックスの唯一の要素です。

 

特定の行列のすべての行で共通の要素を見つけるアルゴリズム

1. Declare a map.
2. Assign all the values of a first row to 1 and stored into the map.
3. Traverse the matrix from the 2nd row of the matrix.
    1. Check if the map contains the current value of the matrix and also the current matrix’s value in a map should be equal to i.
    2. If true, then increase the value of the current matrix’s element frequency in a map by 1.
    3. Put the condition if this is the last row then print all those elements which are common in each row.

説明

M * Nサイズの行列が与えられます。 私たちの仕事は、与えられた行列の各行にも存在するすべての共通要素を見つけることです。 ハッシュ手法を使用してこれを解決します。 素朴なアプローチを使用すると、このコードよりも時間の複雑さが増します。 したがって、O(M * N)時間計算量でそれを解決します。 マップを宣言します。 そのマップでは、値を1に初期化してから、マトリックス内の先の値に進みます。

マップを取得します。行列の最初の行から開始し、最初の行の要素のみのすべての値を1に初期化します。これは、行列のXNUMX番目の行をトラバースするときに発生するためです。 そして、要素が含まれている場合 地図 XNUMX行目にあるものと同じです。 これは、今のところXNUMX行にしか存在しない共通の要素が見つかったことを意味します。

2番目の行からマトリックスのトラバースを開始します。すべての行の各要素がマップに存在するかどうかを確認します。マップに存在する場合は、これがXNUMXであることを意味します。nd マトリックス内のその要素の1番目の行での連続した出現。 選択した各要素の頻度が現在の行と等しいかどうかを確認します。 その要素の頻度の値を更新し、マップ内でXNUMXずつ増やします。 したがって、各トラバーサルについて、i番目の行に等しいかどうかをチェックし、すべての行に連続して存在することを意味します。最後の行のトラバーサルにあるときに、行列のすべての値を出力します。

特定の行列のすべての行に共通の要素

コード

特定の行列のすべての行で共通の要素を見つけるためのC ++コード

#include<iostream>
#include<unordered_map>

#define M 4
#define N 5
using namespace std;


void getCommonElementinRow(int matrix[M][N])
{
    unordered_map<int, int> MAP;

    for (int j = 0; j < N; j++)
        MAP[matrix[0][j]] = 1;

    for (int i = 1; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (MAP[matrix[i][j]] == i)
            {
                MAP[matrix[i][j]] = i + 1;

                if (i==M-1)
                    cout << matrix[i][j] << " ";
            }
        }
    }
}
int main()
{
    int matrix[M][N] = {{12, 1, 4, 5, 9},
        {3, 8, 0, 4, 1},
        {2, 7, 4, 1, 5},
        {6, 3, 1, 9, 4}
    };

    getCommonElementinRow(matrix);

    return 0;
}
1 4

特定の行列のすべての行で共通の要素を見つけるJavaコード

import java.util.HashMap;

class CommonElementsinRow
{
    private static int M = 4;
    private static int N =5;

    static void getCommonElementinRow(int matrix[][])
    {

        HashMap<Integer,Integer> MAP = new HashMap<>();

        for (int j = 0; j < N; j++)
            MAP.put(matrix[0][j],1);

        for (int i = 1; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (MAP.get(matrix[i][j]) != null && MAP.get(matrix[i][j]) == i)
                {

                    MAP.put(matrix[i][j], i + 1);

                    if (i == M - 1)
                        System.out.print(matrix[i][j] + " ");
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int matrix[][] =
        {
            {12, 1, 4, 5, 9},
            {3, 8, 0, 4, 1},
            {2, 7, 4, 1, 5},
            {6, 3, 1, 9, 4}
        };
        getCommonElementinRow(matrix);
    }
}
1 4

 

複雑さの分析

時間の複雑さ

O(m * n) where "m"   「n」 行列の行と列の数です。 HashMapを使用しているため、O(1)時間計算量で挿入やその他の操作を実行できます。 したがって、これにより、O(N * M)時間計算量で実行するアルゴリズムが作成されます。

スペースの複雑さ

O(m * n) where "m"   「n」 行列の行と列の数です。 初期入力自体のサイズはN * Mであるため、空間の複雑さはO(N * M)であると言います。