Dada una array donde cada fila se ordena en orden creciente. Escribe una función que encuentre y devuelva un elemento común en todas las filas. Si no hay un elemento común, devuelve -1.
Ejemplo:
Input: mat[4][5] = { {1, 2, 3, 4, 5},
{2, 4, 5, 8, 10},
{3, 5, 7, 9, 11},
{1, 3, 5, 7, 9},
};
Output: 5
Una solución simple O(m*n*n) es tomar cada elemento de la primera fila y buscarlo en todas las demás filas, hasta que encontremos un elemento común. La complejidad temporal de esta solución es O(m*n*n) donde m es el número de filas y n es el número de columnas en la array dada. Esto se puede mejorar a O(m*n*Logn) si usamos la búsqueda binaria en lugar de la búsqueda lineal.
Podemos resolver este problema en O (mn) de tiempo utilizando un enfoque similar a la fusión de Merge Sort. La idea es comenzar desde la última columna de cada fila. Si los elementos en todas las últimas columnas son iguales, entonces encontramos el elemento común. De lo contrario, encontramos el mínimo de todas las últimas columnas. Una vez que encontramos un elemento mínimo, sabemos que todos los demás elementos en las últimas columnas no pueden ser un elemento común, por lo que reducimos el índice de la última columna para todas las filas, excepto la fila que tiene el valor mínimo. Seguimos repitiendo estos pasos hasta que todos los elementos en la última columna actual no se vuelven iguales, o el índice de la última columna llega a 0.
A continuación se muestra la implementación de la idea anterior.
C++
// A C++ program to find a common element in all rows of a
// row wise sorted array
#include <bits/stdc++.h>
using namespace std;
// Specify number of rows and columns
#define M 4
#define N 5
// Returns common element in all rows of mat[M][N]. If there is no
// common element, then -1 is returned
int findCommon(int mat[M][N])
{
// An array to store indexes of current last column
int column[M];
int min_row; // To store index of row whose current
// last element is minimum
// Initialize current last element of all rows
int i;
for (i = 0; i < M; i++)
column[i] = N - 1;
min_row = 0; // Initialize min_row as first row
// Keep finding min_row in current last column, till either
// all elements of last column become same or we hit first column.
while (column[min_row] >= 0) {
// Find minimum in current last column
for (i = 0; i < M; i++) {
if (mat[i][column[i]] < mat[min_row][column[min_row]])
min_row = i;
}
// eq_count is count of elements equal to minimum in current last
// column.
int eq_count = 0;
// Traverse current last column elements again to update it
for (i = 0; i < M; i++) {
// Decrease last column index of a row whose value is more
// than minimum.
if (mat[i][column[i]] > mat[min_row][column[min_row]]) {
if (column[i] == 0)
return -1;
column[i] -= 1; // Reduce last column index by 1
}
else
eq_count++;
}
// If equal count becomes M, return the value
if (eq_count == M)
return mat[min_row][column[min_row]];
}
return -1;
}
// Driver Code
int main()
{
int mat[M][N] = {
{ 1, 2, 3, 4, 5 },
{ 2, 4, 5, 8, 10 },
{ 3, 5, 7, 9, 11 },
{ 1, 3, 5, 7, 9 },
};
int result = findCommon(mat);
if (result == -1)
cout << "No common element";
else
cout << "Common element is " << result;
return 0;
}
// This code is contributed
// by Akanksha Rai
C
// A C program to find a common element in all rows of a
// row wise sorted array
#include <stdio.h>
// Specify number of rows and columns
#define M 4
#define N 5
// Returns common element in all rows of mat[M][N]. If there is no
// common element, then -1 is returned
int findCommon(int mat[M][N])
{
// An array to store indexes of current last column
int column[M];
int min_row; // To store index of row whose current
// last element is minimum
// Initialize current last element of all rows
int i;
for (i = 0; i < M; i++)
column[i] = N - 1;
min_row = 0; // Initialize min_row as first row
// Keep finding min_row in current last column, till either
// all elements of last column become same or we hit first column.
while (column[min_row] >= 0) {
// Find minimum in current last column
for (i = 0; i < M; i++) {
if (mat[i][column[i]] < mat[min_row][column[min_row]])
min_row = i;
}
// eq_count is count of elements equal to minimum in current last
// column.
int eq_count = 0;
// Traverse current last column elements again to update it
for (i = 0; i < M; i++) {
// Decrease last column index of a row whose value is more
// than minimum.
if (mat[i][column[i]] > mat[min_row][column[min_row]]) {
if (column[i] == 0)
return -1;
column[i] -= 1; // Reduce last column index by 1
}
else
eq_count++;
}
// If equal count becomes M, return the value
if (eq_count == M)
return mat[min_row][column[min_row]];
}
return -1;
}
// driver program to test above function
int main()
{
int mat[M][N] = {
{ 1, 2, 3, 4, 5 },
{ 2, 4, 5, 8, 10 },
{ 3, 5, 7, 9, 11 },
{ 1, 3, 5, 7, 9 },
};
int result = findCommon(mat);
if (result == -1)
printf("No common element");
else
printf("Common element is %d", result);
return 0;
}
Java
// A Java program to find a common
// element in all rows of a
// row wise sorted array
class GFG {
// Specify number of rows and columns
static final int M = 4;
static final int N = 5;
// Returns common element in all rows
// of mat[M][N]. If there is no
// common element, then -1 is
// returned
static int findCommon(int mat[][])
{
// An array to store indexes
// of current last column
int column[] = new int[M];
// To store index of row whose current
// last element is minimum
int min_row;
// Initialize current last element of all rows
int i;
for (i = 0; i < M; i++)
column[i] = N - 1;
// Initialize min_row as first row
min_row = 0;
// Keep finding min_row in current last column, till either
// all elements of last column become same or we hit first column.
while (column[min_row] >= 0) {
// Find minimum in current last column
for (i = 0; i < M; i++) {
if (mat[i][column[i]] < mat[min_row][column[min_row]])
min_row = i;
}
// eq_count is count of elements equal to minimum in current last
// column.
int eq_count = 0;
// Traverse current last column elements again to update it
for (i = 0; i < M; i++) {
// Decrease last column index of a row whose value is more
// than minimum.
if (mat[i][column[i]] > mat[min_row][column[min_row]]) {
if (column[i] == 0)
return -1;
// Reduce last column index by 1
column[i] -= 1;
}
else
eq_count++;
}
// If equal count becomes M,
// return the value
if (eq_count == M)
return mat[min_row][column[min_row]];
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int mat[][] = { { 1, 2, 3, 4, 5 },
{ 2, 4, 5, 8, 10 },
{ 3, 5, 7, 9, 11 },
{ 1, 3, 5, 7, 9 } };
int result = findCommon(mat);
if (result == -1)
System.out.print("No common element");
else
System.out.print("Common element is " + result);
}
}
// This code is contributed by Anant Agarwal.
Python 3
# Python 3 program to find a common element
# in all rows of a row wise sorted array
# Specify number of rows
# and columns
M = 4
N = 5
# Returns common element in all rows
# of mat[M][N]. If there is no common
# element, then -1 is returned
def findCommon(mat):
# An array to store indexes of
# current last column
column = [N - 1] * M
min_row = 0 # Initialize min_row as first row
# Keep finding min_row in current last
# column, till either all elements of
# last column become same or we hit first column.
while (column[min_row] >= 0):
# Find minimum in current last column
for i in range(M):
if (mat[i][column[i]] <
mat[min_row][column[min_row]]):
min_row = i
# eq_count is count of elements equal
# to minimum in current last column.
eq_count = 0
# Traverse current last column elements
# again to update it
for i in range(M):
# Decrease last column index of a row
# whose value is more than minimum.
if (mat[i][column[i]] >
mat[min_row][column[min_row]]):
if (column[i] == 0):
return -1
column[i] -= 1 # Reduce last column
# index by 1
else:
eq_count += 1
# If equal count becomes M, return the value
if (eq_count == M):
return mat[min_row][column[min_row]]
return -1
# Driver Code
if __name__ == "__main__":
mat = [[1, 2, 3, 4, 5],
[2, 4, 5, 8, 10],
[3, 5, 7, 9, 11],
[1, 3, 5, 7, 9]]
result = findCommon(mat)
if (result == -1):
print("No common element")
else:
print("Common element is", result)
# This code is contributed by ita_c
C#
// A C# program to find a common
// element in all rows of a
// row wise sorted array
using System;
class GFG {
// Specify number of rows and columns
static int M = 4;
static int N = 5;
// Returns common element in all rows
// of mat[M][N]. If there is no
// common element, then -1 is
// returned
static int findCommon(int[, ] mat)
{
// An array to store indexes
// of current last column
int[] column = new int[M];
// To store index of row whose
// current last element is minimum
int min_row;
// Initialize current last element
// of all rows
int i;
for (i = 0; i < M; i++)
column[i] = N - 1;
// Initialize min_row as first row
min_row = 0;
// Keep finding min_row in current
// last column, till either all
// elements of last column become
// same or we hit first column.
while (column[min_row] >= 0) {
// Find minimum in current
// last column
for (i = 0; i < M; i++) {
if (mat[i, column[i]] < mat[min_row, column[min_row]])
min_row = i;
}
// eq_count is count of elements
// equal to minimum in current
// last column.
int eq_count = 0;
// Traverse current last column
// elements again to update it
for (i = 0; i < M; i++) {
// Decrease last column index
// of a row whose value is more
// than minimum.
if (mat[i, column[i]] > mat[min_row, column[min_row]]) {
if (column[i] == 0)
return -1;
// Reduce last column index
// by 1
column[i] -= 1;
}
else
eq_count++;
}
// If equal count becomes M,
// return the value
if (eq_count == M)
return mat[min_row,
column[min_row]];
}
return -1;
}
// Driver code
public static void Main()
{
int[, ] mat = { { 1, 2, 3, 4, 5 },
{ 2, 4, 5, 8, 10 },
{ 3, 5, 7, 9, 11 },
{ 1, 3, 5, 7, 9 } };
int result = findCommon(mat);
if (result == -1)
Console.Write("No common element");
else
Console.Write("Common element is "
+ result);
}
}
// This code is contributed by Sam007.
Javascript
<script>
// A Javascript program to find a common
// element in all rows of a
// row wise sorted array
// Specify number of rows and columns
let M = 4;
let N = 5;
// Returns common element in all rows
// of mat[M][N]. If there is no
// common element, then -1 is
// returned
function findCommon(mat)
{
// An array to store indexes
// of current last column
let column=new Array(M);
// To store index of row whose current
// last element is minimum
let min_row;
// Initialize current last element of all rows
let i;
for (i = 0; i < M; i++)
column[i] = N - 1;
// Initialize min_row as first row
min_row = 0;
// Keep finding min_row in current
// last column, till either
// all elements of last column become
// same or we hit first column.
while (column[min_row] >= 0) {
// Find minimum in current last column
for (i = 0; i < M; i++) {
if (mat[i][column[i]] < mat[min_row][column[min_row]])
min_row = i;
}
// eq_count is count of elements equal to
// minimum in current last
// column.
let eq_count = 0;
// Traverse current last column
// elements again to update it
for (i = 0; i < M; i++) {
// Decrease last column index of a row whose value is more
// than minimum.
if (mat[i][column[i]] > mat[min_row][column[min_row]]) {
if (column[i] == 0)
return -1;
// Reduce last column index by 1
column[i] -= 1;
}
else
eq_count++;
}
// If equal count becomes M,
// return the value
if (eq_count == M)
return mat[min_row][column[min_row]];
}
return -1;
}
// Driver Code
let mat = [[1, 2, 3, 4, 5],
[2, 4, 5, 8, 10],
[3, 5, 7, 9, 11],
[1, 3, 5, 7, 9]];
let result = findCommon(mat)
if (result == -1)
{
document.write("No common element");
}
else
{
document.write("Common element is ", result);
}
// This code is contributed by rag2127
</script>
Producción:
Common element is 5
Complejidad temporal: O(M x N).
Espacio Auxiliar: O(M)
Explicación para el funcionamiento del código anterior
. Entendamos el funcionamiento del código anterior para el siguiente ejemplo.
Inicialmente, las entradas en la última array de columnas son N-1, es decir, {4, 4, 4, 4}
{1, 2, 3, 4, 5 },
{2, 4, 5, 8, 10 },
{3, 5 , 7, 9, 11 },
{1, 3, 5, 7, 9 },
el valor de min_row es 0, por lo que los valores del índice de la última columna para filas con un valor superior a 5 se reducen en uno. Entonces columna[] se convierte en {4, 3, 3, 3}.
{1, 2, 3, 4, 5 },
{2, 4, 5, 8 , 10},
{3, 5, 7, 9 , 11},
{1, 3, 5, 7 , 9},
El valor de min_row sigue siendo 0 y el valor del índice de la última columna para las filas con un valor superior a 5 se reduce en uno. Entonces columna[] se convierte en {4, 2, 2, 2}.
{1, 2, 3, 4, 5 },
{2, 4, 5 , 8, 10},
{3, 5, 7 , 9, 11},
{1, 3, 5 , 7, 9},
el valor de min_row sigue siendo 0 y el valor del índice de la última columna para las filas con un valor superior a 5 se reduce en uno. Entonces columna[] se convierte en {4, 2, 1, 2}.
{1, 2, 3, 4, 5 },
{2, 4, 5 , 8, 10},
{3, 5 , 7, 9, 11},
{1, 3, 5 , 7, 9},
Ahora todos los valores en las últimas columnas actuales de todas las filas son iguales, por lo que se devuelve 5.
Una solución basada en hashing
También podemos usar hashing. Esta solución funciona incluso si las filas no están ordenadas. Se puede utilizar para imprimir todos los elementos comunes.
Step1: Create a Hash Table with all key as distinct elements
of row1. Value for all these will be 0.
Step2:
For i = 1 to M-1
For j = 0 to N-1
If (mat[i][j] is already present in Hash Table)
If (And this is not a repetition in current row.
This can be checked by comparing HashTable value with
row number)
Update the value of this key in HashTable with current
row number
Step3: Iterate over HashTable and print all those keys for
which value = M
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Specify number of rows and columns
#define M 4
#define N 5
// Returns common element in all rows of mat[M][N]. If there is no
// common element, then -1 is returned
int findCommon(int mat[M][N])
{
// A hash map to store count of elements
unordered_map<int, int> cnt;
int i, j;
for (i = 0; i < M; i++) {
// Increment the count of first
// element of the row
cnt[mat[i][0]]++;
// Starting from the second element
// of the current row
for (j = 1; j < N; j++) {
// If current element is different from
// the previous element i.e. it is appearing
// for the first time in the current row
if (mat[i][j] != mat[i][j - 1])
cnt[mat[i][j]]++;
}
}
// Find element having count equal to number of rows
for (auto ele : cnt) {
if (ele.second == M)
return ele.first;
}
// No such element found
return -1;
}
// Driver Code
int main()
{
int mat[M][N] = {
{ 1, 2, 3, 4, 5 },
{ 2, 4, 5, 8, 10 },
{ 3, 5, 7, 9, 11 },
{ 1, 3, 5, 7, 9 },
};
int result = findCommon(mat);
if (result == -1)
cout << "No common element";
else
cout << "Common element is " << result;
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Specify number of rows and columns
static int M = 4;
static int N = 5;
// Returns common element in all rows of mat[M][N].
// If there is no common element, then -1 is returned
static int findCommon(int mat[][])
{
// A hash map to store count of elements
HashMap<Integer,
Integer> cnt = new HashMap<Integer,
Integer>();
int i, j;
for (i = 0; i < M; i++)
{
// Increment the count of first
// element of the row
if(cnt.containsKey(mat[i][0]))
{
cnt.put(mat[i][0],
cnt.get(mat[i][0]) + 1);
}
else
{
cnt.put(mat[i][0], 1);
}
// Starting from the second element
// of the current row
for (j = 1; j < N; j++)
{
// If current element is different from
// the previous element i.e. it is appearing
// for the first time in the current row
if (mat[i][j] != mat[i][j - 1])
if(cnt.containsKey(mat[i][j]))
{
cnt.put(mat[i][j],
cnt.get(mat[i][j]) + 1);
}
else
{
cnt.put(mat[i][j], 1);
}
}
}
// Find element having count
// equal to number of rows
for (Map.Entry<Integer,
Integer> ele : cnt.entrySet())
{
if (ele.getValue() == M)
return ele.getKey();
}
// No such element found
return -1;
}
// Driver Code
public static void main(String[] args)
{
int mat[][] = {{ 1, 2, 3, 4, 5 },
{ 2, 4, 5, 8, 10 },
{ 3, 5, 7, 9, 11 },
{ 1, 3, 5, 7, 9 }};
int result = findCommon(mat);
if (result == -1)
System.out.println("No common element");
else
System.out.println("Common element is " + result);
}
}
// This code is contributed by Rajput-Ji
Python
# Python3 implementation of the approach
from collections import defaultdict
# Specify number of rows and columns
M = 4
N = 5
# Returns common element in all rows of
# mat[M][N]. If there is no
# common element, then -1 is returned
def findCommon(mat):
global M
global N
# A hash map to store count of elements
cnt = dict()
cnt = defaultdict(lambda: 0, cnt)
i = 0
j = 0
while (i < M ):
# Increment the count of first
# element of the row
cnt[mat[i][0]] = cnt[mat[i][0]] + 1
j = 1
# Starting from the second element
# of the current row
while (j < N ) :
# If current element is different from
# the previous element i.e. it is appearing
# for the first time in the current row
if (mat[i][j] != mat[i][j - 1]):
cnt[mat[i][j]] = cnt[mat[i][j]] + 1
j = j + 1
i = i + 1
# Find element having count equal to number of rows
for ele in cnt:
if (cnt[ele] == M):
return ele
# No such element found
return -1
# Driver Code
mat = [[1, 2, 3, 4, 5 ],
[2, 4, 5, 8, 10],
[3, 5, 7, 9, 11],
[1, 3, 5, 7, 9 ],]
result = findCommon(mat)
if (result == -1):
print("No common element")
else:
print("Common element is ", result)
# This code is contributed by Arnab Kundu
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Specify number of rows and columns
static int M = 4;
static int N = 5;
// Returns common element in all rows of mat[M,N].
// If there is no common element, then -1 is returned
static int findCommon(int [,]mat)
{
// A hash map to store count of elements
Dictionary<int,
int> cnt = new Dictionary<int,
int>();
int i, j;
for (i = 0; i < M; i++)
{
// Increment the count of first
// element of the row
if(cnt.ContainsKey(mat[i, 0]))
{
cnt[mat[i, 0]]= cnt[mat[i, 0]] + 1;
}
else
{
cnt.Add(mat[i, 0], 1);
}
// Starting from the second element
// of the current row
for (j = 1; j < N; j++)
{
// If current element is different from
// the previous element i.e. it is appearing
// for the first time in the current row
if (mat[i, j] != mat[i, j - 1])
if(cnt.ContainsKey(mat[i, j]))
{
cnt[mat[i, j]]= cnt[mat[i, j]] + 1;
}
else
{
cnt.Add(mat[i, j], 1);
}
}
}
// Find element having count
// equal to number of rows
foreach(KeyValuePair<int, int> ele in cnt)
{
if (ele.Value == M)
return ele.Key;
}
// No such element found
return -1;
}
// Driver Code
public static void Main(String[] args)
{
int [,]mat = {{ 1, 2, 3, 4, 5 },
{ 2, 4, 5, 8, 10 },
{ 3, 5, 7, 9, 11 },
{ 1, 3, 5, 7, 9 }};
int result = findCommon(mat);
if (result == -1)
Console.WriteLine("No common element");
else
Console.WriteLine("Common element is " + result);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Specify number of rows and columns
let M = 4;
let N = 5;
// Returns common element in all rows of mat[M][N].
// If there is no common element, then -1 is returned
function findCommon(mat)
{
// A hash map to store count of elements
let cnt = new Map();
let i, j;
for (i = 0; i < M; i++)
{
// Increment the count of first
// element of the row
if(cnt.has(mat[i][0]))
{
cnt.set(mat[i][0],cnt.get(mat[i][0])+1);
}
else
{
cnt.set(mat[i][0],1);
}
// Starting from the second element
// of the current row
for (j = 1; j < N; j++)
{
// If current element is different from
// the previous element i.e. it is appearing
// for the first time in the current row
if (mat[i][j] != mat[i][j - 1])
{
if(cnt.has(mat[i][j]))
{
cnt.set(mat[i][j], cnt.get(mat[i][j]) + 1);
}
else
{
cnt.set(mat[i][j], 1);
}
}
}
}
// Find element having count
// equal to number of rows
for( let [key, value] of cnt.entries())
{
if(value == M)
return key;
}
// No such element found
return -1;
}
// Driver Code
let mat = [[1, 2, 3, 4, 5 ],
[2, 4, 5, 8, 10],
[3, 5, 7, 9, 11],
[1, 3, 5, 7, 9 ],]
let result = findCommon(mat);
if (result == -1)
document.write("No common element");
else
document.write("Common element is " + result);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Common element is 5
Complejidad de tiempo: O (n * m) bajo el supuesto de que buscar e insertar en HashTable toma O (1) tiempo
Espacio auxiliar: O(n) debido a unordered_map.
Gracias a Nishant por sugerir esta solución en un comentario a continuación.
Ejercicio: dados n arreglos ordenados de tamaño m cada uno, encuentre todos los elementos comunes en todos los arreglos en O (mn) de tiempo.
Este artículo es una contribución de Aarti_Rathi y Anand Agrawal . 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