Знайдзіце розныя элементы, агульныя для ўсіх радкоў матрыцы


Узровень складанасці Жорсткі
Часта пытаюцца ў BlackRock Expedia JP Morgan Qualcomm Snapdeal яйкі Zoho
хэшавання матрыца сартаванне

Пастаноўка праблемы

Нам даецца матрыца ўсіх цэлых лікаў. Задача «Знайсці розныя элементы, агульныя для ўсіх радкоў матрыцы», просіць высветліць усе магчымыя розныя элементы, але агульныя ў кожнай з радкоў, прысутных у матрыцы.

Прыклад

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.

Тлумачэнне

Дадзена матрыца цэлых лікаў. Наша задача - высветліць усе магчымыя значэнні матрыцы, якія адрозніваюцца адзін ад аднаго. А таксама распаўсюджаны ў кожным з радкоў у матрыцы. Мы будзем выкарыстоўваць Set Data Structure для вырашэння гэтага пытання. Гэты набор дадзеных дазваляе дапамагчы выдаліць альбо не прыняць скапіраваныя элементы. Мы будзем пераходзіць матрыцу з другога радка матрыцы. Паколькі першы радок мы ўжо будзем прызначаць для набору.

Мы аб'явім Set, які спачатку называецца SETValue, і дадамо ўсе значэнні першага радка матрыцы ў набор. Гэта толькі таму, што мы павінны праверыць усе элементы, каб яны былі агульнымі ва ўсіх радках. Такім чынам, мы можам выкарыстоўваць першы радок, які будзе прызначаны набору ў якасці спасылкі.

Мы будзем пераходзіць матрыцу зараз з элементаў другога радка, таму што мы ўжо ахапілі першы радок, а цяпер з другога радка возьмем новы Усталёўка Структура дадзеных, па сутнасці, мы будзем прымаць новую структуру дадзеных для кожнага новага радка дадзенай матрыцы ў абходцы. Таму што мы павінны захоўваць гэтыя элементы радкоў у новым наборы, які называецца "temp". Тады мы збіраемся праверыць, ці ёсць якое-небудзь значэнне 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

Аналіз складанасці

Складанасць часу

Тут мы выкарыстоўваем дзве ўкладзеныя цыклы і выкарыстанне unordered_set / HashSet дало нам поліномную складанасць часу. О (н2) дзе "П" - памер матрыцы.

Касмічная складанасць

Аб (п) дзе "П" - гэта памер матрыцы для захоўвання ўваходных дадзеных і захоўвання элементаў у HashSet.