행렬에서 주어진 행의 모든 ​​순열 된 행 찾기


난이도 중급
자주 묻는 질문 24 * 7 Innovation Labs Accenture Expedia 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입니다.th 및 3rd 행은 주어진 행 번호에 대한 순열입니다.

 

행렬에서 주어진 행의 모든 ​​순열 된 행을 찾는 알고리즘

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 인덱스 기반입니다. 우리는 주어진 행이 아닌 다른 행이 주어진 행의 순열인지 알아 내도록 요청했습니다. 여기서 순열은 주어진 요소가 명부 얼마나 많은 목록에서 동일하거나 동일한 목록을 가지고 있는지 여부. 그 행 번호를 인쇄해야합니다. 이를 위해 우리는 세트.

먼저 주어진 행 번호의 모든 값을 집합에 삽입해야합니다. 이것은 이후 작업에서 참조로 취급됩니다. 이 행을 세트에 저장했습니다. 우리는 이것을 자신을 제외한 다른 모든 행과 비교할 것이기 때문입니다.

중첩 루프를 사용하여 이제 행렬을 탐색하십시오. 각 행을 선택하고 해당 행을 사용하여 모든 요소를 ​​순회합니다. 우리가 선택할 행이 주어진 행과 같은 경우 사례를 언급했습니다. 그런 다음 무시하고있는 경우 다음 행으로 이동합니다. 이것은 우리가 답에 하나 이상의 값을 추가하지 않을 것이기 때문입니다. 그리고 그것은 행 자체 인 추가 행을 하나 더 보여줍니다. 그건 받아 들일 수 없습니다. 이제 선택한 행의 요소를 탐색 할 때 선택하는 동안 세트에 세트 요소가 포함되어 있는지 확인합니다. 루프가 전혀 중단되지 않고 나오는 경우, 주어진 행이 순열되고 해당 행 번호를 인쇄 할 것입니다. 더 많은 행이 순열되었는지 여부를 확인하려면 계속 진행하십시오.

행렬에서 주어진 행의 모든 ​​순열 된 행 찾기

암호

행렬에서 주어진 행의 모든 ​​순열 된 행을 찾는 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) 어디에 "엠" 및 "엔" 행렬의 행과 열 수입니다. 우리는 단순히 행렬을 순회하고 HashSet가 O (1)에서 작업을 수행하도록 제공하기 때문에 고소합니다.

공간 복잡성

의 위에) 어디에 "엔" 행렬의 요소 수입니다. 방금 입력을 저장했기 때문에 알고리즘은 선형 공간 복잡성을 갖습니다.