Dada una array mxn, encuentre todos los elementos comunes presentes en todas las filas en tiempo O(mn) y un recorrido de la array.
Ejemplo:
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.
Una solución simple es considerar cada elemento y verificar si está presente en todas las filas. Si está presente, entonces imprímalo.
Una mejor solución es ordenar todas las filas de la array y utilizar un enfoque similar al que se describe aquí . Ordenar tomará un tiempo O(mnlogn) y encontrar elementos comunes tomará un tiempo O(mn). Entonces, la complejidad de tiempo general de esta solución es O (mnlogn)
¿Podemos hacerlo mejor que O (mnlogn)?
La idea es usar mapas. Inicialmente insertamos todos los elementos de la primera fila en un mapa. Para cada otro elemento en las filas restantes, verificamos si está presente en el mapa. Si está presente en el mapa y no está duplicado en la fila actual, incrementamos el recuento del elemento en el mapa en 1; de lo contrario, ignoramos el elemento. Si la fila recorrida actualmente es la última fila, imprimimos el elemento si ha aparecido m-1 veces antes.
A continuación se muestra la implementación de la idea:
C++
// A Program to prints common element in all // rows of matrix #include <bits/stdc++.h> using namespace std; // Specify number of rows and columns #define M 4 #define N 5 // prints common element in all rows of matrix void printCommonElements(int mat[M][N]) { unordered_map<int, int> mp; // initialize 1st row elements with value 1 for (int j = 0; j < N; j++) mp[mat[0][j]] = 1; // traverse the matrix for (int i = 1; i < M; i++) { for (int j = 0; j < N; j++) { // If element is present in the map and // is not duplicated in current row. if (mp[mat[i][j]] == i) { // we increment count of the element // in map by 1 mp[mat[i][j]] = i + 1; // If this is last row if (i==M-1 && mp[mat[i][j]]==M) cout << mat[i][j] << " "; } } } } // driver program to test above function 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
// Java Program to prints common element in all // rows of matrix import java.util.*; class GFG { // Specify number of rows and columns static int M = 4; static int N =5; // prints common element in all rows of matrix static void printCommonElements(int mat[][]) { Map<Integer,Integer> mp = new HashMap<>(); // initialize 1st row elements with value 1 for (int j = 0; j < N; j++) mp.put(mat[0][j],1); // traverse the matrix for (int i = 1; i < M; i++) { for (int j = 0; j < N; j++) { // If element is present in the map and // is not duplicated in current row. if (mp.get(mat[i][j]) != null && mp.get(mat[i][j]) == i) { // we increment count of the element // in map by 1 mp.put(mat[i][j], i + 1); // If this is last row if (i == M - 1) System.out.print(mat[i][j] + " "); } } } } // Driver code 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); } } // This code contributed by Rajput-Ji
Python3
# A Program to prints common element # in all rows of matrix # Specify number of rows and columns M = 4 N = 5 # prints common element in all # rows of matrix def printCommonElements(mat): mp = dict() # initialize 1st row elements # with value 1 for j in range(N): mp[mat[0][j]] = 1 # traverse the matrix for i in range(1, M): for j in range(N): # If element is present in the # map and is not duplicated in # current row. if (mat[i][j] in mp.keys() and mp[mat[i][j]] == i): # we increment count of the # element in map by 1 mp[mat[i][j]] = i + 1 # If this is last row if i == M - 1: print(mat[i][j], end = " ") # Driver Code mat = [[1, 2, 1, 4, 8], [3, 7, 8, 5, 1], [8, 7, 7, 3, 1], [8, 1, 2, 7, 9]] printCommonElements(mat) # This code is contributed # by mohit kumar 29
C#
// C# Program to print common element in all // rows of matrix to another. using System; using System.Collections.Generic; class GFG { // Specify number of rows and columns static int M = 4; static int N = 5; // prints common element in all rows of matrix static void printCommonElements(int [,]mat) { Dictionary<int, int> mp = new Dictionary<int, int>(); // initialize 1st row elements with value 1 for (int j = 0; j < N; j++) { if(!mp.ContainsKey(mat[0, j])) mp.Add(mat[0, j], 1); } // traverse the matrix for (int i = 1; i < M; i++) { for (int j = 0; j < N; j++) { // If element is present in the map and // is not duplicated in current row. if (mp.ContainsKey(mat[i, j])&& (mp[mat[i, j]] != 0 && mp[mat[i, j]] == i)) { // we increment count of the element // in map by 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 this is last row if (i == M - 1) Console.Write(mat[i, j] + " "); } } } } // Driver code 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); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript Program to prints common element in all // rows of matrix // Specify number of rows and columns let M = 4; let N =5; // prints common element in all rows of matrix function printCommonElements(mat) { let mp = new Map(); // initialize 1st row elements with value 1 for (let j = 0; j < N; j++) mp.set(mat[0][j],1); // traverse the matrix for (let i = 1; i < M; i++) { for (let j = 0; j < N; j++) { // If element is present in the map and // is not duplicated in current row. if (mp.get(mat[i][j]) != null && mp.get(mat[i][j]) == i) { // we increment count of the element // in map by 1 mp.set(mat[i][j], i + 1); // If this is last row if (i == M - 1) document.write(mat[i][j] + " "); } } } } // Driver code let mat = [[1, 2, 1, 4, 8], [3, 7, 8, 5, 1], [8, 7, 7, 3, 1], [8, 1, 2, 7, 9]] printCommonElements(mat) // This code is contributed by unknown2108 </script>
8 1
La complejidad temporal de esta solución es O(m * n) y solo estamos haciendo un recorrido de la array.
Espacio Auxiliar : O(N)
Este artículo es una contribución de Aarti_Rathi y Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA