Dada una array mat[][] de tamaño M * N , la tarea es encontrar todos los elementos de la array que sean mínimos en sus respectivas filas y máximos en sus respectivas columnas. Si tal elemento no está presente, imprima -1 .
Ejemplos:
Entrada: mat[][] = {{1, 10, 4}, {9, 3, 8}, {15, 16, 17}}
Salida: 15
Explicación:
15 es el único elemento que es máximo en su columna { 1, 3, 15 } y mínimo en su fila { 15 , 16, 17}.Entrada: m[][] = {{10, 41}, {3, 5}, {16, 2}}
Salida: -1
Enfoque: siga los pasos a continuación para resolver el problema:
- Cree un conjunto_desordenado y almacene el elemento mínimo de cada fila de la array.
- Recorra la array y encuentre el elemento máximo de cada columna. Para cada columna, verifique si el máximo obtenido ya está presente en unordered_set o no.
- Si se encuentra que es cierto, imprima ese número. Si no se encuentra tal elemento de array, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Functionto find all the matrix elements
// which are minimum in its row and maximum
// in its column
vector<int> minmaxNumbers(vector<vector<int> >& matrix,
vector<int>& res)
{
// Initialize unordered set
unordered_set<int> set;
// Traverse the matrix
for (int i = 0; i < matrix.size(); i++) {
int minr = INT_MAX;
for (int j = 0; j < matrix[i].size(); j++) {
// Update the minimum
// element of current row
minr = min(minr, matrix[i][j]);
}
// Insert the minimum
// element of the row
set.insert(minr);
}
for (int j = 0; j < matrix[0].size(); j++) {
int maxc = INT_MIN;
for (int i = 0; i < matrix.size(); i++) {
// Update the maximum
// element of current column
maxc = max(maxc, matrix[i][j]);
}
// Checking if it is already present
// in the unordered_set or not
if (set.find(maxc) != set.end()) {
res.push_back(maxc);
}
}
return res;
}
// Driver Code
int main()
{
vector<vector<int> > mat
= { { 1, 10, 4 },
{ 9, 3, 8 },
{ 15, 16, 17 } };
vector<int> ans;
// Function call
minmaxNumbers(mat, ans);
// If no such matrix
// element is found
if (ans.size() == 0)
cout << "-1" << endl;
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Functionto find all the matrix elements
// which are minimum in its row and maximum
// in its column
public static Vector<Integer>minmaxNumbers(int[][] matrix,
Vector<Integer> res)
{
// Initialize unordered set
Set<Integer> set = new HashSet<Integer>();
// Traverse the matrix
for(int i = 0; i < matrix.length; i++)
{
int minr = Integer.MAX_VALUE;
for(int j = 0; j < matrix[i].length; j++)
{
// Update the minimum
// element of current row
minr = Math.min(minr, matrix[i][j]);
}
// Insert the minimum
// element of the row
set.add(minr);
}
for(int j = 0; j < matrix[0].length; j++)
{
int maxc = Integer.MIN_VALUE;
for(int i = 0; i < matrix.length; i++)
{
// Update the maximum
// element of current column
maxc = Math.max(maxc, matrix[i][j]);
}
// Checking if it is already present
// in the unordered_set or not
if (set.contains(maxc))
{
res.add(maxc);
}
}
return res;
}
// Driver code
public static void main(String[] args)
{
int[][] mat = { { 1, 10, 4 },
{ 9, 3, 8 },
{ 15, 16, 17 } };
Vector<Integer> ans = new Vector<Integer>();
// Function call
ans = minmaxNumbers(mat, ans);
// If no such matrix
// element is found
if (ans.size() == 0)
System.out.println("-1");
for(int i = 0; i < ans.size(); i++)
System.out.println(ans.get(i));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach
import sys
# Functionto find all the matrix elements
# which are minimum in its row and maximum
# in its column
def minmaxNumbers(matrix, res):
# Initialize unordered set
s = set()
# Traverse the matrix
for i in range(0, len(matrix), 1):
minr = sys.maxsize
for j in range(0, len(matrix[i]), 1):
# Update the minimum
# element of current row
minr = min(minr, matrix[i][j])
# Insert the minimum
# element of the row
s.add(minr)
for j in range(0, len(matrix[0]), 1):
maxc = -sys.maxsize - 1
for i in range(0, len(matrix), 1):
# Update the maximum
# element of current column
maxc = max(maxc, matrix[i][j])
# Checking if it is already present
# in the unordered_set or not
if (maxc in s):
res.append(maxc)
return res
# Driver Code
if __name__ == '__main__':
mat = [ [ 1, 10, 4 ],
[ 9, 3, 8 ],
[ 15, 16, 17 ] ]
ans = []
# Function call
minmaxNumbers(mat, ans)
# If no such matrix
# element is found
if (len(ans) == 0):
print("-1")
for i in range(len(ans)):
print(ans[i])
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Functionto find all
// the matrix elements
// which are minimum
// in its row and
// maximum in its column
public static List<int> minmaxNumbers(int[,] matrix,
List<int> res)
{
// Initialize unordered set
HashSet<int> set = new HashSet<int>();
// Traverse the matrix
for(int i = 0; i < matrix.GetLength(0); i++)
{
int minr = int.MaxValue;
for(int j = 0; j < matrix.GetLength(1); j++)
{
// Update the minimum
// element of current row
minr = Math.Min(minr, matrix[i, j]);
}
// Insert the minimum
// element of the row
set.Add(minr);
}
for(int j = 0; j < matrix.GetLength(0); j++)
{
int maxc = int.MinValue;
for(int i = 0; i < matrix.GetLength(1); i++)
{
// Update the maximum
// element of current column
maxc = Math.Max(maxc, matrix[i, j]);
}
// Checking if it is already present
// in the unordered_set or not
if (set.Contains(maxc))
{
res.Add(maxc);
}
}
return res;
}
// Driver code
public static void Main(String[] args)
{
int[,] mat = {{1, 10, 4},
{9, 3, 8},
{15, 16, 17}};
List<int> ans = new List<int>();
// Function call
ans = minmaxNumbers(mat, ans);
// If no such matrix
// element is found
if (ans.Count == 0)
Console.WriteLine("-1");
for(int i = 0; i < ans.Count; i++)
Console.WriteLine(ans[i]);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Functionto find all the matrix elements
// which are minimum in its row and maximum
// in its column
function minmaxNumbers(matrix, res)
{
// Initialize unordered set
var set = new Set();
// Traverse the matrix
for (var i = 0; i < matrix.length; i++) {
var minr = 1000000000;
for (var j = 0; j < matrix[i].length; j++) {
// Update the minimum
// element of current row
minr = Math.min(minr, matrix[i][j]);
}
// Insert the minimum
// element of the row
set.add(minr);
}
for (var j = 0; j < matrix[0].length; j++) {
var maxc = -1000000000;
for (var i = 0; i < matrix.length; i++) {
// Update the maximum
// element of current column
maxc = Math.max(maxc, matrix[i][j]);
}
// Checking if it is already present
// in the unordered_set or not
if (set.has(maxc)) {
res.push(maxc);
}
}
return res;
}
// Driver Code
var mat
= [ [ 1, 10, 4 ],
[ 9, 3, 8 ],
[ 15, 16, 17 ] ];
var ans = [];
// Function call
minmaxNumbers(mat, ans);
// If no such matrix
// element is found
if (ans.length == 0)
document.write( "-1");
for (var i = 0; i < ans.length; i++)
document.write( ans[i] + "<br>");
// This code is contributed by rrrtnx.
</script>
Producción:
15
Complejidad temporal: O(M * N)
Espacio auxiliar: O(M + N)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA