행렬의 모든 행에 공통적 인 고유 요소 찾기

난이도 하드
자주 묻는 질문 BlackRock Expedia JP 모건 퀄컴 스냅 딜 야 트라 조호 (Zoho)
해싱 매트릭스 정렬조회수 92

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

모든 정수의 행렬이 주어집니다. "행렬의 모든 행에 공통적 인 고유 요소 찾기"문제는 가능한 모든 고유 요소를 찾아야하지만 행렬에있는 각 행에는 공통입니다.

arr[]={ {11, 12, 3, 10},

{11, 5, 8, 3},

{7, 11, 3, 10},

{9, 10, 11, 3}}
3 11

설명 : 3과 11은 주어진 행렬의 각 행에서 고유하고 공통적 인 두 숫자입니다.

행렬의 모든 행에 공통적 인 고유 요소를 찾는 알고리즘

1. Declare a Set “SETValue”.
2. Add all the values of the first row of a matrix into the “SETValue”.
3. Traverse the matrix from the second row of a given matrix.
  1. Declare a new set let’s say “temp”, every time for each row of a matrix.
    1. Add all the values of that particular row in “temp” Set.
  2. Iterate over the set “SETValue” in which we stored our first row values.
    1. Check if temp contains any of the value of SETValue.
      1. If it contains, then removes that value from the SETValue.
  3. If SETValue size is equal to 0, then break the loop.
4. Traverse SETValue and print all the values in it.

설명

정수 행렬이 주어집니다. 우리의 임무는 서로 구별되는 행렬의 가능한 모든 값을 찾는 것입니다. 또한 행렬의 각 행에서 공통입니다. 이 문제를 해결하는 데 데이터 구조 설정을 사용할 것입니다. 이 세트 데이터 구조는 복사 된 요소를 제거하거나 허용하지 않는 데 도움이됩니다. 행렬의 두 번째 행에서 행렬을 순회합니다. 첫 번째 행이 이미 세트에 할당되어 있기 때문입니다.

먼저 SETValue라는 Set을 선언하고 행렬의 첫 번째 행의 모든 ​​값을 집합에 추가합니다. 이는 모든 행에서 공통되어야하는 모든 요소를 ​​확인해야하기 때문입니다. 따라서 우리는 Set에 할당 될 첫 번째 행을 참조로 사용할 수 있습니다.

우리는 이미 첫 번째 행을 다루었으므로 이제 두 번째 행 요소에서 행렬을 순회 할 것이며 이제 두 번째 행에서 새로운 세트 실제로 데이터 구조는 순회에서 주어진 행렬의 각 새 행에 대해 새로운 데이터 구조를 취합니다. 특정 행 요소를 "temp"라는 새 Set에 저장해야하기 때문입니다. 그런 다음 SETValue의 값이 temp에 있는지 확인하고 해당 요소를 제거합니다. 또한 널 포인터 예외 값을 확인하기 위해 하나의 조건을 거기에 두었습니다. SETValue 세트의 크기가 0이되면 루프가 중단되고 런타임 오류가 발생하지 않습니다.

SETValue에서 요소를 제거 할 때 순회 후 출력 값이 있으므로 해당 값을 인쇄합니다.

행렬의 모든 행에 공통적 인 고유 요소 찾기

암호

행렬의 모든 행에 공통적 인 고유 요소를 찾기위한 C ++ 코드

#include<unordered_set>
#include<iostream>

using namespace std;

const int MAX = 100;

void getDistinctCommonElements (int mat[][MAX], int n)
{
    unordered_set<int> SETValue;

    for (int i=0; i<n; i++)
        SETValue.insert(mat[0][i]);

    for (int i=1; i<n; i++)
    {
        unordered_set<int> temp;

        for (int j=0; j<n; j++)
            temp.insert(mat[i][j]);

        unordered_set<int>:: iterator itr;

        for (itr=SETValue.begin(); itr!=SETValue.end(); itr++)

            if (temp.find(*itr) == temp.end())
                SETValue.erase(*itr);

        if (SETValue.size() == 0)
            break;
    }
    unordered_set<int>:: iterator itr;
    for (itr=SETValue.begin(); itr!=SETValue.end(); itr++)
        cout << *itr << " ";
}
int main()
{
    int mat[][MAX] =  { {11, 12, 3, 10},
        {11, 5, 8, 3},
        {7, 11, 3, 1},
        {9, 0, 11, 3}
    };
    int n = 4;
    getDistinctCommonElements (mat, n);
    return 0;
}
3 11

행렬의 모든 행에 공통적 인 고유 요소를 찾는 Java 코드

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Collection;

class DistinctCommonElements
{
    public static void getDistinctCommonElements(int mat[][], int n)
    {
        Collection<Integer> removeElements = new LinkedList<Integer>();
        HashSet<Integer> SETValue=new HashSet<>();

        for (int i=0; i<n; i++)
            SETValue.add(mat[0][i]);

        for (int i=1; i<n; i++)
        {
            HashSet<Integer> temp= new HashSet<Integer>();
            for (int j=0; j<n; j++)
                temp.add(mat[i][j]);

            for(Integer element : SETValue)
                if(!(temp.contains(element)))
                    removeElements.add(element);

            SETValue.removeAll(removeElements);

            if (SETValue.size() == 0)
                break;
        }
        Iterator<Integer> itr=SETValue.iterator();
        while(itr.hasNext())
            System.out.print(itr.next()+" ");
    }
    public static void main(String [] args)
    {
        int mat[][] = { {11, 12, 3, 10},
            {11, 5, 8, 3},
            {7, 11, 3, 10},
            {9, 10, 11, 3}
        };
        int n = 4;
        getDistinctCommonElements (mat, n);
    }
}
3 11

복잡성 분석

시간 복잡성

여기서 우리는 두 개의 중첩 된 루프를 사용하고 있으며 unorder_set / HashSet을 사용하여 다항식 시간 복잡성을 제공했습니다. 의 위에2) 어디에 "엔" 행렬의 크기입니다.

공간 복잡성

O (N) 어디에 "엔" 입력을 저장하고 HashSet에 요소를 저장하기위한 행렬의 크기입니다.

균열 시스템 설계 인터뷰
Translate »