Рубрики

Общие элементы во всех строках данной матрицы

Учитывая матрицу mxn, найдите все общие элементы, присутствующие во всех строках за O (mn) времени и один обход матрицы.

Пример:

Input:
mat[4][5] = {{1, 2, 1, 4, 8},
             {3, 7, 8, 5, 1},
             {8, 7, 7, 3, 1},
             {8, 1, 2, 7, 9},
            };

Output: 
1 8 or 8 1
8 and 1 are present in all rows.

Простое решение — рассмотреть каждый элемент и проверить, присутствует ли он во всех строках. Если он есть, распечатайте его.

Лучшим решением является сортировка всех строк в матрице и использование аналогичного подхода, как обсуждалось здесь . Сортировка займет O (mnlogn) времени, а поиск общих элементов займет O (mn) времени. Таким образом, общая временная сложность этого решения составляет O (mnlogn)

Можем ли мы сделать лучше, чем O (Mnlogn)?
Идея состоит в том, чтобы использовать карты. Мы изначально вставляем все элементы первого ряда в карту. Для каждого другого элемента в оставшихся строках мы проверяем, присутствует ли он на карте. Если он присутствует на карте и не дублируется в текущей строке, мы увеличиваем счетчик элемента в карте на 1, иначе мы игнорируем элемент. Если текущая пройденная строка является последней строкой, мы печатаем элемент, если он появлялся m-1 раз ранее.

Ниже приведена реализация идеи.

C ++

// Программа для печати общего элемента во всех
// строки матрицы
#include <iostream>
#include <unordered_map>

using namespace std;

  
// Укажите количество строк и столбцов
#define M 4
#define N 5

  
// печатает общий элемент во всех строках матрицы

void printCommonElements(int mat[M][N])

{

    unordered_map<int, int> mp;

  

    // инициализируем элементы 1-й строки значением 1

    for (int j = 0; j < N; j++)

        mp[mat[0][j]] = 1;

  

    // пройти матрицу

    for (int i = 1; i < M; i++)

    {

        for (int j = 0; j < N; j++)

        {

            // Если элемент присутствует на карте и

            // не дублируется в текущей строке.

            if (mp[mat[i][j]] == i)

            {

               // увеличиваем количество элементов

               // в карте по 1

                mp[mat[i][j]] = i + 1;

  

                // Если это последняя строка

                if (i==M-1)

                  cout << mat[i][j] << " ";

            }

        }

    }

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    int mat[M][N] =

    {

        {1, 2, 1, 4, 8},

        {3, 7, 8, 5, 1},

        {8, 7, 7, 3, 1},

        {8, 1, 2, 7, 9},

    };

  

    printCommonElements(mat);

  

    return 0;

}

Джава

// Java-программа для печати общего элемента во всех
// строки матрицы

import java.util.*;

  

class GFG 

{

  
// Укажите количество строк и столбцов

static int M = 4;

static int N =5;

  
// печатает общий элемент во всех строках матрицы

static void printCommonElements(int mat[][])

{

  

    Map<Integer,Integer> mp = new HashMap<>();

      

    // инициализируем элементы 1-й строки значением 1

    for (int j = 0; j < N; j++)

        mp.put(mat[0][j],1);

          

    // пройти матрицу

    for (int i = 1; i < M; i++)

    {

        for (int j = 0; j < N; j++)

        {

            // Если элемент присутствует на карте и

            // не дублируется в текущей строке.

            if (mp.get(mat[i][j]) != null && mp.get(mat[i][j]) == i)

            {

                // увеличиваем количество элементов

                // в карте по 1

                mp.put(mat[i][j], i + 1);

  

                // Если это последняя строка

                if (i == M - 1)

                    System.out.print(mat[i][j] + " ");

            }

        }

    }

}

  
// Код драйвера

public static void main(String[] args) 

{

    int mat[][] =

    {

        {1, 2, 1, 4, 8},

        {3, 7, 8, 5, 1},

        {8, 7, 7, 3, 1},

        {8, 1, 2, 7, 9},

    };

  

    printCommonElements(mat);

}
}

  
// Этот код предоставлен Rajput-Ji

python3

# Программа для печати общего элемента
# во всех строках матрицы

  
# Укажите количество строк и столбцов

M = 4

N = 5

  
# печатает общий элемент во всех
# строк матрицы

def printCommonElements(mat):

  

    mp = dict()

  

    # инициализировать элементы 1-го ряда

    # со значением 1

    for j in range(N):

        mp[mat[0][j]] = 1

  

    # пройти матрицу

    for i in range(1, M):

        for j in range(N):

              

            # Если элемент присутствует в

            # карта и не дублируется в

            # текущая строка.

            if (mat[i][j] in mp.keys() and

                             mp[mat[i][j]] == i):

                                   

            # мы увеличиваем количество

            # элемент в карте на 1

                mp[mat[i][j]] = i + 1

  

                # Если это последний ряд

                if i == M - 1:

                    print(mat[i][j], end = " ")

              
Код водителя

mat = [[1, 2, 1, 4, 8],

       [3, 7, 8, 5, 1],

       [8, 7, 7, 3, 1],

       [8, 1, 2, 7, 9]]

  
printCommonElements(mat)

  
# Этот код предусмотрен
# от mohit kumar 29

C #

// C # Программа для печати общего элемента во всех
// строки матрицы в другую.

using System; 

using System.Collections.Generic; 

  

class GFG 

{

  
// Укажите количество строк и столбцов

static int M = 4;

static int N = 5;

  
// печатает общий элемент во всех строках матрицы

static void printCommonElements(int [,]mat)

{

  

    Dictionary<int, int> mp = new Dictionary<int, int>();

      

    // инициализируем элементы 1-й строки значением 1

    for (int j = 0; j < N; j++)

    {

        if(!mp.ContainsKey(mat[0, j]))

            mp.Add(mat[0, j], 1);

    }

      

    // пройти матрицу

    for (int i = 1; i < M; i++)

    {

        for (int j = 0; j < N; j++)

        {

            // Если элемент присутствует на карте и

            // не дублируется в текущей строке.

            if (mp.ContainsKey(mat[i, j])&&

               (mp[mat[i, j]] != 0 && 

                mp[mat[i, j]] == i))

            {

                // увеличиваем количество элементов

                // в карте по 1

                if(mp.ContainsKey(mat[i, j]))

                {

                    var v = mp[mat[i, j]];

                    mp.Remove(mat[i, j]);

                    mp.Add(mat[i, j], i + 1);

                }

                else

                    mp.Add(mat[i, j], i + 1);

  

                // Если это последняя строка

                if (i == M - 1)

                    Console.Write(mat[i, j] + " ");

            }

        }

    }

}

  
// Код драйвера

public static void Main(String[] args) 

{

    int [,]mat = {{1, 2, 1, 4, 8},

                  {3, 7, 8, 5, 1},

                  {8, 7, 7, 3, 1},

                  {8, 1, 2, 7, 9}};

  

    printCommonElements(mat);

}
}

  
// Этот код предоставлен 29AjayKumar


Выход:

8 1

Временная сложность этого решения составляет O (m * n), и мы делаем только один обход матрицы.

Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Общие элементы во всех строках данной матрицы

0.00 (0%) 0 votes