주어진 행렬의 모든 행에있는 공통 요소

난이도 중급
자주 묻는 질문 아마존 시스코 드 쇼 운영 SAP 연구소 조호 (Zoho)
배열 해시 해싱 매트릭스조회수 45

문제 정책

“주어진 행렬의 모든 행에있는 공통 요소”문제는 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로 초기화합니다. 이는 행렬의 두 번째 행을 탐색 할 때 때문입니다. 그리고 우리가 지도 두 번째 행에있는 것과 동일합니다. 즉, 지금은 두 행에만있는 공통 요소를 찾았습니다.

이제 두 번째 행에서 행렬을 탐색하기 시작합니다. 모든 행의 각 요소가 맵에 있는지 확인합니다. 맵에 있으면 이것이 2임을 의미합니다.nd 두 번째 행에서 연속적으로 행렬에서 해당 요소의 발생. 선택한 각 요소 빈도가 현재 행과 같은지 확인합니다. 해당 요소의 빈도 값을 업데이트하고 맵에서 1 씩 늘립니다. 따라서 각 순회에 대해 해당 빈도가 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) 어디에 "엠" 및 "엔" 행렬의 행과 열 수입니다. HashMap을 사용하기 때문에 O (1) 시간 복잡도로 삽입 및 기타 작업을 수행 할 수 있습니다. 따라서 이것은 O (N * M) 시간 복잡도로 실행되는 알고리즘을 만듭니다.

공간 복잡성

O (m * n) 어디에 "엠" 및 "엔" 행렬의 행과 열 수입니다. 초기 입력 자체의 크기는 N * M이므로 공간 복잡도는 O (N * M)입니다.

Translate »