Пронађите различите елементе заједничке свим редовима матрице


Ниво тешкоће Тежак
Често питани у Блацкроцк Екпедиа ЈП Морган куалцомм Снапдеал Иатра Зохо
Хасхинг матрица сортирање

Изјава о проблему

Добијамо матрицу свих целих бројева. Проблем „Пронађи различите елементе заједничке свим редовима матрице“ тражи да се открију сви могући различити елементи, али заједнички у сваком од редова присутних у матрици.

Пример

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.

Објашњење

Дата је матрица целих бројева. Наш задатак је да откријемо све могуће вредности матрице које се међусобно разликују. И такође уобичајени у сваком од редова у матрици. У решавању овог питања користићемо Сет Структура података. Овај скуп података структура помаже у уклањању или неприхватању копираних елемената. Прећи ћемо матрицу из другог реда матрице. Зато што ћемо први ред већ бити додељени скупу.

Декларисаћемо Сет који се прво назива СЕТВалуе и додати све вредности првог реда матрице у скуп. То је само зато што морамо да проверимо све елементе да ли би требали бити заједнички у свим редовима. Тако можемо користити први ред који ће бити додељен скупу као референцу.

Прећи ћемо матрицу сада из елемената другог реда, јер смо већ покрили први ред, а сада ћемо из другог реда узети нови Сет Структура података, у ствари, узимаћемо нову структуру података за сваки нови ред дате матрице у преласку. Зато што морамо да сачувамо те одређене елементе реда у новом скупу званом „темп“. Тада ћемо проверити да ли је нека од вредности СЕТВалуе присутна у темп иф присутан онда ћемо уклонити тај елемент. Такође, тамо смо поставили један услов за проверу вредности изузетка нулл показивача. Ако величина СЕТВалуе скупа постане 0, тада ће прекинути петљу и неће бити грешке у извршавању.

Како уклањамо елементе из СЕТВалуе, тамо имамо излазну вредност након преласка, па ћемо те вредности штампати.

Пронађите различите елементе заједничке свим редовима матрице

код

Ц ++ код за проналажење различитих елемената заједничких за све редове матрице

#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

Јава код за проналажење различитих елемената заједничких за све редове матрице

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

Анализа сложености

Сложеност времена

Овде смо користили две угнежђене петље и коришћење неуређеног_сета / ХасхСет-а нам је дало полиномску временску сложеност. На2) где „Н“ је величина матрице.

Сложеност простора

Он) где „Н“ је величина матрице, за чување улаза и чување елемената у ХасхСет-у.