Матрицаның барлық жолдарына тән ерекше элементтерді табыңыз


Күрделілік дәрежесі қиын
Жиі кіреді BlackRock Expedia JP Morgan Qualcomm Шапшаң Yatra Зохо
Хэш Matrix Сұрыптау

Проблемалық мәлімдеме

Бізге барлық бүтін сандардың матрицасы берілген. «Матрицаның барлық жолдарына ортақ жеке элементтерді табу» мәселесі матрицада кездесетін барлық жолдардың бәрін анықтауға мүмкіндік береді.

мысал

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 деп аталатын жиынтығын жариялаймыз және жиынға матрицаның бірінші жолының барлық мәндерін қосамыз. Бұл барлық элементтерде кездесетін барлық элементтерді тексеруіміз керек болғандықтан. Осылайша, біз анықтамалық ретінде жиынға берілетін бірінші жолды қолдана аламыз.

Біз қазір матрицаны екінші қатар элементтерінен өтеміз, өйткені біз бірінші жолды жауып тастадық, ал енді екінші қатардан біз жаңа жолды аламыз жиынтық Деректер құрылымы, шын мәнінде, біз өтпелі матрицаның әрбір жаңа жолдары үшін жаңа деректер құрылымын аламыз. Біз белгілі бір жол элементтерін «уақыт» деп аталатын жаңа жиынтықта сақтауымыз керек. Содан кейін SETValue мәнінің кез-келгені уақытша болса, бар-жоғын тексереміз, содан кейін біз бұл элементті алып тастаймыз. Сонымен, біз нөлдік көрсеткіштің ерекше мәнін тексеру үшін бір шарт қойдық. Егер SETValue жиынының өлшемі 0-ге айналса, онда ол циклды бұзады және жұмыс уақытында қате болмайды.

SETValue ішінен элементтерді алып тастаған кезде, өтпеден кейін бізде шығыс мәні бар, сондықтан біз сол мәндерді басып шығарамыз.

Матрицаның барлық жолдарына тән ерекше элементтерді табыңыз

код

С ++ коды матрицаның барлық жолдарына ортақ элементтерді табуға арналған

#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

Күрделілікті талдау

Уақыттың күрделілігі

Міне, біз екі кірістірілген циклды қолдандық және unordered_set / HashSet көмегімен полиномдық уақыттың күрделілігі пайда болды. O (n2) қайда «N» матрицаның өлшемі болып табылады.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл HashSet ішіндегі кірісті және элементтерді сақтауға арналған матрицаның өлшемі.