行列内の特定の行のすべての並べ替えられた行を検索します


難易度 ミディアム
よく聞かれる 24 * 7イノベーションラボ アクセンチュア エクスペディア IBM JPモルガン Quora
配列 ハッシュ ハッシング マトリックス

問題文

行列内の特定の行のすべての並べ替えられた行を検索すると、サイズm * nの行列が与えられ、行列の行番号は「行」と表示されます。 問題ステートメントは、指定された行への順列である可能性のあるすべての行を見つけるように要求します。 これは、各行のすべての要素が異なるとも言われています。

r = 2

mat[][] = {{6, 5, 9, 2},

{1, 6, 9, 3},

{6, 5, 9, 2},

{6, 2, 5, 9}}
0, 3

説明:指定された行は2で、6、5、2、および9が含まれています。これは0のみです。th そして、3rd rowは、指定された行番号の順列です。

 

行列内の特定の行のすべての並べ替えられた行を見つけるアルゴリズム

1. Create a set.
2. Insert the given row elements into the set.
3. Traverse the matrix, and ignore the given row number while traversing.
    1. Check if the set doesn’t contain each value of the traversed row if it doesn’t contain then break the loop and proceed for next row.
    2. Else print the value of i, i.e, the current row number.

 

説明

たとえば、m行n列の行列と行番号が与えられます。与えられた行番号は0インデックスベースです。 与えられた行の順列である与えられた行以外の行列の行かどうかを調べるように依頼しました。 ここでの順列は、与えられた要素の要素が リスト リストの数が同じであるか、同じリストを持っているかどうか。 その行番号を印刷する必要があります。 このために、私たちは使用するつもりです 作成セッションプロセスで.

まず、指定された行番号のすべての値をセットに挿入する必要があります。 これは、後の操作で参照として扱われます。 この行をセットに保存しました。 これを、それ自体を除く他のすべての行と比較するためです。

ネストされたループを使用して、マトリックスをトラバースします。 各行を選択し、その行を使用して、そのすべての要素をトラバースします。 ピックアップする行が指定された行と同じである場合について説明しました。 次に、それを無視し、存在する場合は次の行に移動します。 これは、答えにもうXNUMXつの値を追加しないためです。 そして、それは行自体であるもうXNUMXつの余分な行を示しています。 それは受け入れられないでしょう。 ここで、選択した行の要素をトラバースするときに、選択するときにセットにセット要素が含まれているかどうかを確認します。 ループがまったく壊れずに出てきた場合、つまり、指定された行が並べ替えられ、その行番号が出力されます。 さらに進んで、より多くの行が並べ替えられているかどうかを確認します。

行列内の特定の行のすべての並べ替えられた行を検索します

コード

行列内の特定の行のすべての並べ替えられた行を検索するC ++コード

#include<iostream>
#include<unordered_set>

#define MAX 100

using namespace std;

void checkPermutatedRow(int matrix[][MAX], int m, int n, int r)
{
    unordered_set<int> s;

    for (int j=0; j<n; j++)
        s.insert(matrix[r][j]);

    for (int i=0; i<m; i++)
    {
        if (i==r)
            continue;

        int j;
        for (j=0; j<n; j++)
            if (s.find(matrix[i][j]) == s.end())
                break;
        if (j != n)
            continue;

        cout << i << ", ";
    }
}
int main()
{
    int row = 4, col = 4,r = 2;
    int matrix[][MAX] = {{6, 5, 9, 2},
        {1, 6, 9, 3},
        {6, 5, 9, 2},
        {6, 2, 5, 9}
    };
    checkPermutatedRow(matrix, row, col, r);
    return 0;
}
0, 3,

行列内の特定の行のすべての並べ替えられた行を検索するJavaコード

import java.util.LinkedHashSet;

class Permutations
{
    private static int MAX = 100;

    public static void checkPermutatedRow(int matrix[][], int m, int n, int r)
    {
        LinkedHashSet<Integer> SET = new LinkedHashSet<>();

        for (int j = 0; j < n; j++)
            SET.add(matrix[r][j]);

        for (int i = 0; i < m; i++)
        {
            if (i == r)
                continue;

            int j;
            for (j = 0; j < n; j++)
                if (!SET.contains(matrix[i][j]))
                    break;
            if (j != n)
                continue;

            System.out.print(i+", ");
        }
    }
    public static void main(String[] args)
    {
        int  row= 4, col = 4,r = 2;
        int matrix[][] = {{6, 5, 9, 2},
            {1, 6, 9, 3},
            {6, 5, 9, 2},
            {6, 2, 5, 9}
        };
        checkPermutatedRow(matrix, row, col, r);
    }
}
0, 3,

 

複雑さの分析

時間の複雑さ

O(m * n) where "m"   「n」 行列の行と列の数です。 単純にマトリックスをトラバースし、HashSetを使用して、O(1)で操作を実行するために提供されます。

スペースの複雑さ

オン) where "N" 行列内の要素の数です。 入力を保存したばかりなので、アルゴリズムには線形空間の複雑さがあります。