Знайдіть різні елементи, загальні для всіх рядків матриці


Рівень складності Жорсткий
Часто запитують у 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, який спочатку називається SETValue, і додамо всі значення першого рядка матриці до набору. Це лише тому, що ми повинні перевірити всі елементи, щоб вони були загальними у всіх рядках. Отже, ми можемо використовувати перший рядок, який буде призначений набору як еталон.

Ми будемо переходити матрицю зараз з елементів другого рядка, тому що ми вже перекрили перший рядок, а тепер з другого рядка ми будемо брати новий Установка Структура даних, насправді, ми будемо брати нову Структуру даних для кожного нового рядка даної матриці в обхідному режимі. Тому що ми маємо зберігати ці конкретні елементи рядків у новому наборі, який називається “temp”. Тоді ми будемо перевіряти, чи є значення SETValue в temp, якщо воно присутнє, тоді ми збираємось видалити цей елемент. Крім того, ми поставили там одну умову, щоб перевірити значення виключення нульового покажчика. Якщо розмір набору 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

Аналіз складності

Складність часу

Тут ми використовували дві вкладені петлі, а використання невпорядкованого_набору / HashSet дало нам поліноміальну часову складність. О (н.)2) де "N" - розмір матриці.

Складність простору

О (п) де "N" - це розмір матриці для зберігання вхідних даних та зберігання елементів у HashSet.