Dada una array xn. El problema es encontrar todos los elementos distintos comunes a todas las filas de la array. Los elementos se pueden imprimir en cualquier orden.
Ejemplos:
Input : mat[][] = { {2, 1, 4, 3},
{1, 2, 3, 2},
{3, 6, 2, 3},
{5, 2, 5, 3} }
Output : 2 3
Input : mat[][] = { {12, 1, 14, 3, 16},
{14, 2, 1, 3, 35},
{14, 1, 14, 3, 11},
{14, 25, 3, 2, 1},
{1, 18, 3, 21, 14} }
Output : 1 3 14
Método 1: usar tres bucles anidados. Compruebe si un elemento de la primera fila está presente en todas las filas posteriores. Complejidad temporal de O(n 3 ). Es posible que se requiera espacio adicional para manejar los elementos duplicados.
Método 2: Ordene todas las filas de la array individualmente en orden creciente. Luego aplique un enfoque modificado al problema de encontrar elementos comunes en 3 arreglos ordenados . A continuación se da una implementación para el mismo.
C++
// C++ implementation to find distinct elements
// common to all rows of a matrix
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
// function to individually sort
// each row in increasing order
void sortRows(int mat[][MAX], int n)
{
for (int i=0; i<n; i++)
sort(mat[i], mat[i] + n);
}
// function to find all the common elements
void findAndPrintCommonElements(int mat[][MAX], int n)
{
// sort rows individually
sortRows(mat, n);
// current column index of each row is stored
// from where the element is being searched in
// that row
int curr_index[n];
memset(curr_index, 0, sizeof(curr_index));
int f = 0;
for (; curr_index[0]<n; curr_index[0]++)
{
// value present at the current column index
// of 1st row
int value = mat[0][curr_index[0]];
bool present = true;
// 'value' is being searched in all the
// subsequent rows
for (int i=1; i<n; i++)
{
// iterate through all the elements of
// the row from its current column index
// till an element greater than the 'value'
// is found or the end of the row is
// encountered
while (curr_index[i] < n &&
mat[i][curr_index[i]] <= value)
curr_index[i]++;
// if the element was not present at the column
// before to the 'curr_index' of the row
if (mat[i][curr_index[i]-1] != value)
present = false;
// if all elements of the row have
// been traversed
if (curr_index[i] == n)
{
f = 1;
break;
}
}
// if the 'value' is common to all the rows
if (present)
cout << value << " ";
// if any row have been completely traversed
// then no more common elements can be found
if (f == 1)
break;
}
}
// Driver program to test above
int main()
{
int mat[][MAX] = { {12, 1, 14, 3, 16},
{14, 2, 1, 3, 35},
{14, 1, 14, 3, 11},
{14, 25, 3, 2, 1},
{1, 18, 3, 21, 14}
};
int n = 5;
findAndPrintCommonElements(mat, n);
return 0;
}
Java
// JAVA Code to find distinct elements
// common to all rows of a matrix
import java.util.*;
class GFG {
// function to individually sort
// each row in increasing order
public static void sortRows(int mat[][], int n)
{
for (int i=0; i<n; i++)
Arrays.sort(mat[i]);
}
// function to find all the common elements
public static void findAndPrintCommonElements(int mat[][],
int n)
{
// sort rows individually
sortRows(mat, n);
// current column index of each row is stored
// from where the element is being searched in
// that row
int curr_index[] = new int[n];
int f = 0;
for (; curr_index[0]<n; curr_index[0]++)
{
// value present at the current column index
// of 1st row
int value = mat[0][curr_index[0]];
boolean present = true;
// 'value' is being searched in all the
// subsequent rows
for (int i=1; i<n; i++)
{
// iterate through all the elements of
// the row from its current column index
// till an element greater than the 'value'
// is found or the end of the row is
// encountered
while (curr_index[i] < n &&
mat[i][curr_index[i]] <= value)
curr_index[i]++;
// if the element was not present at the
// column before to the 'curr_index' of the
// row
if (mat[i][curr_index[i]-1] != value)
present = false;
// if all elements of the row have
// been traversed
if (curr_index[i] == n)
{
f = 1;
break;
}
}
// if the 'value' is common to all the rows
if (present)
System.out.print(value+" ");
// if any row have been completely traversed
// then no more common elements can be found
if (f == 1)
break;
}
}
/* Driver program to test above function */
public static void main(String[] args)
{
int mat[][] = { {12, 1, 14, 3, 16},
{14, 2, 1, 3, 35},
{14, 1, 14, 3, 11},
{14, 25, 3, 2, 1},
{1, 18, 3, 21, 14}
};
int n = 5;
findAndPrintCommonElements(mat, n);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 implementation to find distinct # elements common to all rows of a matrix MAX = 100 # function to individually sort # each row in increasing order def sortRows(mat, n): for i in range(0, n): mat[i].sort(); # function to find all the common elements def findAndPrintCommonElements(mat, n): # sort rows individually sortRows(mat, n) # current column index of each row is # stored from where the element is being # searched in that row curr_index = [0] * n for i in range (0, n): curr_index[i] = 0 f = 0 while(curr_index[0] < n): # value present at the current # column index of 1st row value = mat[0][curr_index[0]] present = True # 'value' is being searched in # all the subsequent rows for i in range (1, n): # iterate through all the elements # of the row from its current column # index till an element greater than # the 'value' is found or the end of # the row is encountered while (curr_index[i] < n and mat[i][curr_index[i]] <= value): curr_index[i] = curr_index[i] + 1 # if the element was not present at # the column before to the 'curr_index' # of the row if (mat[i][curr_index[i] - 1] != value): present = False # if all elements of the row have # been traversed) if (curr_index[i] == n): f = 1 break # if the 'value' is common to all the rows if (present): print(value, end = " ") # if any row have been completely traversed # then no more common elements can be found if (f == 1): break curr_index[0] = curr_index[0] + 1 # Driver Code mat = [[12, 1, 14, 3, 16], [14, 2, 1, 3, 35], [14, 1, 14, 3, 11], [14, 25, 3, 2, 1], [1, 18, 3, 21, 14]] n = 5 findAndPrintCommonElements(mat, n) # This code is contributed by iAyushRaj
C#
// C# Code to find distinct elements
// common to all rows of a matrix
using System;
class GFG
{
// function to individually sort
// each row in increasing order
public static void sortRows(int[][] mat, int n)
{
for (int i = 0; i < n; i++)
{
Array.Sort(mat[i]);
}
}
// function to find all the common elements
public static void findAndPrintCommonElements(int[][] mat,
int n)
{
// sort rows individually
sortRows(mat, n);
// current column index of each row is stored
// from where the element is being searched in
// that row
int[] curr_index = new int[n];
int f = 0;
for (; curr_index[0] < n; curr_index[0]++)
{
// value present at the current column index
// of 1st row
int value = mat[0][curr_index[0]];
bool present = true;
// 'value' is being searched in all the
// subsequent rows
for (int i = 1; i < n; i++)
{
// iterate through all the elements of
// the row from its current column index
// till an element greater than the 'value'
// is found or the end of the row is
// encountered
while (curr_index[i] < n &&
mat[i][curr_index[i]] <= value)
{
curr_index[i]++;
}
// if the element was not present at the column
// before to the 'curr_index' of the row
if (mat[i][curr_index[i] - 1] != value)
{
present = false;
}
// if all elements of the row have
// been traversed
if (curr_index[i] == n)
{
f = 1;
break;
}
}
// if the 'value' is common to all the rows
if (present)
{
Console.Write(value + " ");
}
// if any row have been completely traversed
// then no more common elements can be found
if (f == 1)
{
break;
}
}
}
// Driver Code
public static void Main(string[] args)
{
int[][] mat = new int[][]
{
new int[] {12, 1, 14, 3, 16},
new int[] {14, 2, 1, 3, 35},
new int[] {14, 1, 14, 3, 11},
new int[] {14, 25, 3, 2, 1},
new int[] {1, 18, 3, 21, 14}
};
int n = 5;
findAndPrintCommonElements(mat, n);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript Code to find distinct elements
// common to all rows of a matrix
// function to individually sort
// each row in increasing order
function sortRows(mat,n)
{
for (let i=0; i<n; i++)
mat[i].sort(function(a,b){return a-b;});
}
// function to find all the common elements
function findAndPrintCommonElements(mat,n)
{
// sort rows individually
sortRows(mat, n);
// current column index of each row is stored
// from where the element is being searched in
// that row
let curr_index = new Array(n);
for(let i=0;i<n;i++)
{
curr_index[i]=0;
}
let f = 0;
for (; curr_index[0]<n; curr_index[0]++)
{
// value present at the current column index
// of 1st row
let value = mat[0][curr_index[0]];
let present = true;
// 'value' is being searched in all the
// subsequent rows
for (let i=1; i<n; i++)
{
// iterate through all the elements of
// the row from its current column index
// till an element greater than the 'value'
// is found or the end of the row is
// encountered
while (curr_index[i] < n &&
mat[i][curr_index[i]] <= value)
curr_index[i]++;
// if the element was not present at the
// column before to the 'curr_index' of the
// row
if (mat[i][curr_index[i]-1] != value)
present = false;
// if all elements of the row have
// been traversed
if (curr_index[i] == n)
{
f = 1;
break;
}
}
// if the 'value' is common to all the rows
if (present)
document.write(value+" ");
// if any row have been completely traversed
// then no more common elements can be found
if (f == 1)
break;
}
}
/* Driver program to test above function */
let mat = [[12, 1, 14, 3, 16],
[14, 2, 1, 3, 35],
[14, 1, 14, 3, 11],
[14, 25, 3, 2, 1],
[1, 18, 3, 21, 14]]
let n = 5;
findAndPrintCommonElements(mat, n);
// This code is contributed by patel2127
</script>
Producción:
1 3 14
Complejidad de tiempo: O (n 2 log n), cada fila de tamaño n requiere O (nlogn) para ordenar y hay un total de n filas.
Espacio auxiliar: O(n) para almacenar índices de columna actuales para cada fila.
Método 3: Utiliza el concepto de hashing. Los siguientes pasos son:
- Asigne el elemento de la primera fila en una tabla hash. Que sea hachís .
- Fow fila = 2 a n
- Asigne cada elemento de la fila actual a una tabla hash temporal. Que sea temporal .
- Itere a través de los elementos de hash y verifique que los elementos de hash estén presentes en temp . Si no está presente, elimine esos elementos del hash .
- Cuando todas las filas se procesan de esta manera, los elementos que quedan en hash son los elementos comunes requeridos.
C++
// C++ program to find distinct elements
// common to all rows of a matrix
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
// function to individually sort
// each row in increasing order
void findAndPrintCommonElements(int mat[][MAX], int n)
{
unordered_set<int> us;
// map elements of first row
// into 'us'
for (int i=0; i<n; i++)
us.insert(mat[0][i]);
for (int i=1; i<n; i++)
{
unordered_set<int> temp;
// mapping elements of current row
// in 'temp'
for (int j=0; j<n; j++)
temp.insert(mat[i][j]);
unordered_set<int>:: iterator itr;
// iterate through all the elements
// of 'us'
for (itr=us.begin(); itr!=us.end(); itr++)
// if an element of 'us' is not present
// into 'temp', then erase that element
// from 'us'
if (temp.find(*itr) == temp.end())
us.erase(itr++);
else
itr++;
// if size of 'us' becomes 0,
// then there are no common elements
if (us.size() == 0)
break;
}
// print the common elements
unordered_set<int>:: iterator itr;
for (itr=us.begin(); itr!=us.end(); itr++)
cout << *itr << " ";
}
// Driver program to test above
int main()
{
int mat[][MAX] = { {2, 1, 4, 3},
{1, 2, 3, 2},
{3, 6, 2, 3},
{5, 2, 5, 3} };
int n = 4;
findAndPrintCommonElements(mat, n);
return 0;
}
Java
// Java program to find distinct elements
// common to all rows of a matrix
import java.util.*;
class GFG{
static int MAX = 100;
// function to individually sort
// each row in increasing order
@SuppressWarnings("unchecked")
static void findAndPrintCommonElements(int mat[][], int n)
{
HashSet<Integer> us = new HashSet<Integer>();
// map elements of first row
// into 'us'
for (int i = 0; i < n; i++)
us.add(mat[0][i]);
for (int i = 1; i < n; i++)
{
HashSet<Integer> temp = new HashSet<Integer>();
// mapping elements of current row
// in 'temp'
for (int j = 0; j < n; j++)
temp.add(mat[i][j]);
HashSet<Integer> itr=(HashSet<Integer>) us.clone();
// iterate through all the elements
// of 'us'
for (int x :itr)
// if an element of 'us' is not present
// into 'temp', then erase that element
// from 'us'
if (!temp.contains(x))
us.remove(x);
// if size of 'us' becomes 0,
// then there are no common elements
if (us.size() == 0)
break;
}
// print the common elements
HashSet<Integer> itr1=(HashSet<Integer>) us.clone();
for (int x :itr1)
System.out.print(x+ " ");
}
// Driver program to test above
public static void main(String[] args)
{
int mat[][] = { {2, 1, 4, 3},
{1, 2, 3, 2},
{3, 6, 2, 3},
{5, 2, 5, 3} };
int n = 4;
findAndPrintCommonElements(mat, n);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to find distinct elements # common to all rows of a matrix MAX = 100 # function to individually sort # each row in increasing order def findAndPrintCommonElements(mat, n): us = dict() # map elements of first row # into 'us' for i in range(n): us[mat[0][i]] = 1 for i in range(1, n): temp = dict() # mapping elements of current row # in 'temp' for j in range(n): temp[mat[i][j]] = 1 # iterate through all the elements # of 'us' for itr in list(us): # if an element of 'us' is not present # into 'temp', then erase that element # from 'us' if itr not in temp: del us[itr] # if size of 'us' becomes 0, # then there are no common elements if (len(us) == 0): break # print common elements for itr in list(us)[::-1]: print(itr, end = " ") # Driver Code mat = [[2, 1, 4, 3], [1, 2, 3, 2], [3, 6, 2, 3], [5, 2, 5, 3]] n = 4 findAndPrintCommonElements(mat, n) # This code is contributed by Mohit Kumar
C#
// C# program to find distinct elements
// common to all rows of a matrix
using System;
using System.Collections.Generic;
public class GFG{
static int MAX = 100;
// function to individually sort
// each row in increasing order
static void findAndPrintCommonElements(int [,]mat, int n)
{
HashSet<int> us = new HashSet<int>();
// map elements of first row
// into 'us'
for (int i = 0; i < n; i++)
us.Add(mat[0, i]);
for (int i = 1; i < n; i++)
{
HashSet<int> temp = new HashSet<int>();
// mapping elements of current row
// in 'temp'
for (int j = 0; j < n; j++)
temp.Add(mat[i,j]);
HashSet<int> itr=new HashSet<int>(us);
// iterate through all the elements
// of 'us'
foreach (int x in itr)
// if an element of 'us' is not present
// into 'temp', then erase that element
// from 'us'
if (!temp.Contains(x))
us.Remove(x);
// if size of 'us' becomes 0,
// then there are no common elements
if (us.Count == 0)
break;
}
// print the common elements
HashSet<int> itr1=new HashSet<int>(us);
foreach (int x in itr1)
Console.Write(x+ " ");
}
// Driver program to test above
public static void Main(String[] args)
{
int [,]mat = { {2, 1, 4, 3},
{1, 2, 3, 2},
{3, 6, 2, 3},
{5, 2, 5, 3} };
int n = 4;
findAndPrintCommonElements(mat, n);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to find distinct elements
// common to all rows of a matrix
var MAX = 100;
// function to individually sort
// each row in increasing order
function findAndPrintCommonElements(mat, n)
{
var us = new Set();
// map elements of first row
// into 'us'
for (var i = 0; i < n; i++)
us.add(mat[0][i]);
for(var i = 1; i < n; i++)
{
var temp = new Set();
// mapping elements of current row
// in 'temp'
for (var j = 0; j < n; j++)
temp.add(mat[i][j]);
// iterate through all the elements
// of 'us'
for(var itr of us)
{
// if an element of 'us' is not present
// into 'temp', then erase that element
// from 'us'
if(!temp.has(itr))
us.delete(itr);
}
// if size of 'us' becomes 0,
// then there are no common elements
if (us.size == 0)
break;
}
// print the common elements
for(var itr of [...us].sort((a,b)=>b-a))
document.write( itr + " ");
}
// Driver program to test above
var mat = [ [2, 1, 4, 3],
[1, 2, 3, 2],
[3, 6, 2, 3],
[5, 2, 5, 3]];
var n = 4;
findAndPrintCommonElements(mat, n);
// This code is contributed by noob2000.
</script>
Producción:
3 2
Complejidad temporal: O(n 2 )
Complejidad espacial: O(n)
Método 4: Uso del mapa
- Inserta todos los elementos de la 1ra fila en el mapa.
- Ahora verificamos que los elementos presentes en el mapa estén presentes en cada fila o no.
- Si el elemento está presente en el mapa y no está duplicado en la fila actual, incrementamos el recuento del elemento en el mapa en 1.
- Si llegamos a la última fila durante el recorrido y si el elemento aparece (N-1) veces antes, imprimimos el elemento.
C++
// C++ program to find distinct elements
// common to all rows of a matrix
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
// function to individually sort
// each row in increasing order
void distinct(int mat[][MAX], int N)
{
// make a empty map
unordered_map<int,int> ans;
// Insert the elements of
// first row in the map and
// initialize with 1
for (int j = 0; j < N; j++) {
ans[mat[0][j]]=1;
}
// Traverse the matrix from 2nd row
for (int i = 1; i < N; i++) {
for (int j = 0; j < N; j++) {
// If the element is present in the map
// and is not duplicated in the current row
if (ans[mat[i][j]] != 0
&& ans[mat[i][j]] == i) {
// Increment count of the element in
// map by 1
ans[mat[i][j]]= i + 1;
// If we have reached the last row
if (i == N - 1) {
// Print the element
cout<<mat[i][j]<<" ";
}
}
}
}
}
// Driver program to test above
int main()
{
int N=4;
int mat[][MAX] = { {2, 1, 4, 3},
{1, 2, 3, 2},
{3, 6, 2, 3},
{5, 2, 5, 3} };
distinct(mat, N);
return 0;
}
// This code is Contributed by Aarti_Rathi
Java
// JAVA Code to find distinct elements
// common to all rows of a matrix
import java.io.*;
import java.util.*;
class GFG {
static void distinct(int matrix[][], int N)
{
// make a empty map
Map<Integer, Integer> ans = new HashMap<>();
// Insert the elements of
// first row in the map and
// initialize with 1
for (int j = 0; j < N; j++) {
ans.put(matrix[0][j], 1);
}
// Traverse the matrix from 2nd row
for (int i = 1; i < N; i++) {
for (int j = 0; j < N; j++) {
// If the element is present in the map
// and is not duplicated in the current row
if (ans.get(matrix[i][j]) != null
&& ans.get(matrix[i][j]) == i) {
// Increment count of the element in
// map by 1
ans.put(matrix[i][j], i + 1);
// If we have reached the last row
if (i == N - 1) {
// Print the element
System.out.print(matrix[i][j]
+ " ");
}
}
}
}
}
/* Driver program to test above function */
public static void main(String[] args)
{
int matrix[][] = { { 2, 1, 4, 3 },
{ 1, 2, 3, 2 },
{ 3, 6, 2, 3 },
{ 5, 2, 5, 3 } };
int n = 4;
distinct(matrix, n);
}
}
// This code is Contributed by Darshit Shukla
Python3
# Python code to find distinct elements
# common to all rows of a matrix
def distinct(matrix, N):
# Make a empty map
ans = {}
# Insert the elements of
# first row in the map and
# initialize with 1
for j in range(N):
ans[matrix[0][j]] = 1
# Traverse the matrix from 2nd row
for i in range(N):
for j in range(N):
# If the element is present in the map
# and is not duplicated in the current row
if matrix[i][j] in ans and ans[matrix[i][j]] == i:
# Increment count of the element in
# map by 1
ans[matrix[i][j]] = i + 1
# If we have reached the last row
if (i == N - 1):
# Print the element
print(matrix[i][j],end=" ")
# Driver code
matrix = [ [ 2, 1, 4, 3 ],
[ 1, 2, 3, 2 ],
[ 3, 6, 2, 3 ],
[ 5, 2, 5, 3 ] ]
n = 4
distinct(matrix, n)
# This code is contributed by shinjanpatra
C#
// C# code to find distinct elements
// common to all rows of a matrix
using System;
using System.Collections.Generic;
class GFG{
static void distinct(int[,] matrix, int N)
{
// Make a empty map
Dictionary<int,
int> ans = new Dictionary<int,
int>();
// Insert the elements of
// first row in the map and
// initialize with 1
for(int j = 0; j < N; j++)
{
ans[matrix[0, j]] = 1;
}
// Traverse the matrix from 2nd row
for(int i = 1; i < N; i++)
{
for(int j = 0; j < N; j++)
{
// If the element is present in the map
// and is not duplicated in the current row
if (ans.ContainsKey(matrix[i, j]) &&
ans[matrix[i, j]] == i)
{
// Increment count of the element in
// map by 1
ans[matrix[i, j]] = i + 1;
// If we have reached the last row
if (i == N - 1)
{
// Print the element
Console.Write(matrix[i, j] + " ");
}
}
}
}
}
// Driver code
public static void Main(string[] args)
{
int[,] matrix = { { 2, 1, 4, 3 },
{ 1, 2, 3, 2 },
{ 3, 6, 2, 3 },
{ 5, 2, 5, 3 } };
int n = 4;
distinct(matrix, n);
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript code to find distinct elements
// common to all rows of a matrix
function distinct(matrix, N)
{
// Make a empty map
var ans = new Map()
// Insert the elements of
// first row in the map and
// initialize with 1
for(var j = 0; j < N; j++)
{
ans.set(matrix[0][j], 1);
}
// Traverse the matrix from 2nd row
for(var i = 1; i < N; i++)
{
for(var j = 0; j < N; j++)
{
// If the element is present in the map
// and is not duplicated in the current row
if (ans.has(matrix[i][j]) &&
ans.get(matrix[i][j]) == i)
{
// Increment count of the element in
// map by 1
ans.set(matrix[i][j], i + 1);
// If we have reached the last row
if (i == N - 1)
{
// Print the element
document.write(matrix[i][j] + " ");
}
}
}
}
}
// Driver code
var matrix = [ [ 2, 1, 4, 3 ],
[ 1, 2, 3, 2 ],
[ 3, 6, 2, 3 ],
[ 5, 2, 5, 3 ] ];
var n = 4;
distinct(matrix, n);
// This code is contributed by rutvik_56.
</script>
Producción:
2 3
Complejidad temporal: O(n 2 )
Complejidad espacial: O(n)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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