Dada una array cuadrada M[][] de tamaño N x N , la tarea es encontrar los máximos y mínimos de cada una de las filas y columnas , multiplicar los máximos y mínimos correspondientes de cada fila con los de cada columna, finalmente devolver el diferencia absoluta de ambos.
Ejemplos :
Entrada: M[][] = [ [ 3, 2, 5 ], [ 7, 5, 4 ], [ 7, 2, 9 ] ]
Salida: 11
Explicación :
Entrada: M = [ [1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
Salida: 40
Enfoque ingenuo: la tarea se puede resolver simulando las operaciones dadas. Siga los pasos a continuación para resolver el problema:
- Tome 2 arrays max1[ ] y min1[ ] para almacenar el máximo y el mínimo de cada fila o cada columna.
- Primero almacene el máximo de cada fila en max1[ ] y el mínimo de cada fila en min1[ ] .
- Múltiple matrix y return res, guárdelo en R .
- Tome la transposición de la array M[ ] .
- Luego almacene el máximo de cada columna en max1[ ] y el mínimo de cada columna en min1[ ] .
- Multiplique ambas arrays y devuelva res, guárdelo en C .
- Imprima la diferencia absoluta de R y C .
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;
// Function to find the transpose matrix M[]
vector<vector<int>> transpose(vector<vector<int>>M, int N){
for(int i = 0; i < N; i++)
{
for(int j = 0; j < i + 1; j++)
{
int temp = M[i][j];
M[i][j] = M[j][i];
M[j][i] = temp;
}
}
return M;
}
// Function to convert matrix M[][] to size 1 * 1
int matOne(vector<vector<int>>M, int N)
{
// Max1 and min1 to store max and min
// of each row pr column
vector<int>max1;
vector<int>min1;
// Loop to store element in max1 and min1
for(int r = 0; r < N; r++)
{
max1.push_back(*max_element(M[r].begin(), M[r].end()));
min1.push_back(*min_element(M[r].begin(), M[r].end()));
}
// Initialise res to 0
int res = 0;
// Multiply and add both array
for(int i = 0; i < N; i++){
res += max1[i]*min1[i];
}
// Return res
return res;
}
// Driver code
int main()
{
// Original matrix
vector<vector<int>>M = {{3, 2, 5},{7, 5, 4},{7, 2, 9}};
// N size of matrix
int N = M.size();
// Call matOne function for rows
int R = matOne(M, N);
// Transpose the matrix
vector<vector<int>>T = transpose(M, N);
// Call matOne function for column
int C = matOne(T, N);
// Print the absolute difference
cout << abs(R - C) << endl;
}
// This code is contributed by shinjanpatra
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to find the transpose matrix M[]
static int[][] transpose(int[][] M, int N) {
int transpose[][] = new int[N][N];
// Code to transpose a matrix
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
transpose[i][j] = M[j][i];
}
}
return transpose;
}
// Function to convert matrix M[][] to size 1 * 1
static int matOne(int[][] M, int N) {
// Max1 and min1 to store max and min
// of each row pr column
ArrayList<Integer> max1 = new ArrayList<Integer>();
ArrayList<Integer> min1 = new ArrayList<Integer>();
// Loop to calculate res.
for (int[] r : M)
{
max1.add(Arrays.stream(r).max().getAsInt());
min1.add(Arrays.stream(r).min().getAsInt());
}
// Initialise res to 0
int res = 0;
// Multiply and add both array
for(int i = 0; i < N; i++)
{
res += max1.get(i)*min1.get(i);
}
// Return res
return res;
}
// Driver code
public static void main(String[] args)
{
// Original matrix
int[][] M = { { 3, 2, 5 }, { 7, 5, 4 }, { 7, 2, 9 } };
// N size of matrix
int N = M.length;
// Call matOne function for rows
int R = matOne(M, N);
// Transpose the matrix
int[][] T = transpose(M, N);
// Call matOne function for column
int C = matOne(T, N);
// Print the absolute difference
System.out.println((Math.abs(R - C)));
}
}
// This code is contributed by aditya patil
Python3
# Python program for the above approach # Function to find the transpose matrix M[] def transpose(M, N): for i in range(N): for j in range(i + 1): M[i][j], M[j][i] = M[j][i], M[i][j] return M # Function to convert matrix M[][] to size 1 * 1 def matOne(M, N): # Max1 and min1 to store max and min # of each row pr column max1 = [] min1 = [] # Loop to store element in max1 and min1 for r in M: max1.append(max(r)) min1.append(min(r)) # Initialise res to 0 res = 0 # Multiply and add both array for i in range(N): res += max1[i]*min1[i] # Return res return res # Driver code if __name__ == "__main__": # Original matrix M = [[3, 2, 5], [7, 5, 4], [7, 2, 9]] # N size of matrix N = len(M) # Call matOne function for rows R = matOne(M, N) # Transpose the matrix T = transpose(M, N) # Call matOne function for column C = matOne(T, N) # Print the absolute difference print(str(abs(R-C)))
Javascript
<script>
// Javascript program for the above approach
// Function to find the transpose matrix M[]
function transpose(M) {
return M[0].map((col, i) => M.map(row => row[i]));
}
// Function to convert matrix M[][] to size 1 * 1
function matOne(M, N) {
// Max1 and min1 to store max and min
// of each row pr column
let max1 = []
let min1 = []
// Loop to store element in max1 and min1
for (r of M){
max1.push([...r].sort((a, b) => b - a)[0])
min1.push([...r].sort((a, b) => a - b)[0])
}
// Initialise res to 0
let res = 0
// Multiply and add both array
for (let i = 0; i < N; i++)
res += max1[i] * min1[i]
// Return res
return res
}
// Driver code
// Original matrix
let M = [[3, 2, 5], [7, 5, 4], [7, 2, 9]];
// N size of matrix
let N = M.length;
// Call matOne function for rows
let R = matOne(M, N)
// Transpose the matrix
let T = transpose(M)
// Call matOne function for column
let C = matOne(T, N)
// Print the absolute difference
document.write(Math.abs(R - C))
// This code is contributed by saurabh_jaiswal.
</script>
Producción
11
Tiempo Complejidad :O(N 2 )
Espacio Auxiliar :O(N)
Enfoque de optimización del espacio: este enfoque es similar al enfoque 1, pero en este, el espacio auxiliar se optimizará al no usar arreglos max1 y min1. En esto, dirija múltiples y agregue el elemento y devuélvalo.
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;
// Function to find the transpose matrix M[]
vector<vector<int>> transpose(vector<vector<int>>M, int N){
for(int i = 0; i < N; i++)
{
for(int j = 0; j < i + 1; j++)
{
int temp = M[i][j];
M[i][j] = M[j][i];
M[j][i] = temp;
}
}
return M;
}
// Function to convert matrix M[][] to size 1 * 1
int matOne(vector<vector<int>>M, int N)
{
// Max1 and min1 to store max and min
// of each row pr column
vector<int>arr;
int res = 0;
for (int r =0;r< N;r++){
arr.clear();
for(int j =0;j<N;j++){
arr.push_back(M[r][j]);
}
sort(arr.begin(),arr.end());
res += arr[arr.size()-1] * arr[0];
}
// Return res
return res;
}
// Driver code
int main()
{
// Original matrix
vector<vector<int>>M = {{3, 2, 5},{7, 5, 4},{7, 2, 9}};
// N size of matrix
int N = M.size();
// Call matOne function for rows
int R = matOne(M, N);
// Transpose the matrix
vector<vector<int>>T = transpose(M, N);
// Call matOne function for column
int C = matOne(T, N);
// Print the absolute difference
cout << abs(R - C) << endl;
}
// This code is contributed by akshitsaxenaa09.
Java
import java.util.Arrays;
// Java program for the above approach
class GFG
{
// Function to find the transpose matrix M[]
static int[][] transpose(int[][] M, int N) {
int transpose[][] = new int[N][N];
// Code to transpose a matrix
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
transpose[i][j] = M[j][i];
}
}
return transpose;
}
// Function to convert matrix M[][] to size 1 * 1
static int matOne(int[][] M, int N) {
// Loop to calculate res.
int res = 0;
for (int[] r : M)
res += Arrays.stream(r).max().getAsInt() * Arrays.stream(r).min().getAsInt();
// Return res
return res;
}
// Driver code
public static void main(String[] args)
{
// Original matrix
int[][] M = { { 3, 2, 5 }, { 7, 5, 4 }, { 7, 2, 9 } };
// N size of matrix
int N = M.length;
// Call matOne function for rows
int R = matOne(M, N);
// Transpose the matrix
int[][] T = transpose(M, N);
// Call matOne function for column
int C = matOne(T, N);
// Print the absolute difference
System.out.println((Math.abs(R - C)));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for the above approach # Function to find the transpose matrix M[] def transpose(M, N): for i in range(N): for j in range(i + 1): M[i][j], M[j][i] = M[j][i], M[i][j] return M # Function to convert matrix M[][] to size 1 * 1 def matOne(M, N): # Loop to calculate res. res = 0 for r in M: res += max(r)*min(r) # Return res return res # Driver code if __name__ == "__main__": # Original matrix M = [[3, 2, 5], [7, 5, 4], [7, 2, 9]] # N size of matrix N = len(M) # Call matOne function for rows R = matOne(M, N) # Transpose the matrix T = transpose(M, N) # Call matOne function for column C = matOne(T, N) # Print the absolute difference print(str(abs(R-C)))
C#
// C# program for the above approach
using System;
using System.Linq;
public class GFG
{
// Function to find the transpose matrix []M
static int[,] transpose(int[,] M, int N)
{
int [,]transpose = new int[N,N];
// Code to transpose a matrix
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
transpose[i,j] = M[j,i];
}
}
return transpose;
}
// Function to convert matrix [,]M to size 1 * 1
static int matOne(int[,] M, int N) {
// Loop to calculate res.
int res = 0;
for (int r =0;r< N;r++){
int[] t = new int[N];
for(int j =0;j<N;j++){
t[j] = M[r,j];
}
res += t.Max() * t.Min();
}
// Return res
return res;
}
// Driver code
public static void Main(String[] args)
{
// Original matrix
int[,] M = { { 3, 2, 5 }, { 7, 5, 4 }, { 7, 2, 9 } };
// N size of matrix
int N = M.GetLength(0);
// Call matOne function for rows
int R = matOne(M, N);
// Transpose the matrix
int[,] T = transpose(M, N);
// Call matOne function for column
int C = matOne(T, N);
// Print the absolute difference
Console.WriteLine((Math.Abs(R - C)));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// JavaScript code for the above approach
// Function to find the transpose matrix M[]
function transpose(M, N)
{
// This function stores transpose
// of A in B
let B = Array(M).fill(0);
for (let i = 0; i < N; i++) {
B[i] = new Array(N);
}
var i, j;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
B[i][j] = M[j][i];
return B
}
// Function to convert matrix M[][] to size 1 * 1
function matOne(M, N) {
// Max1 and min1 to store max and min
// of each row pr column
max1 = []
min1 = []
// Loop to store element in max1 and min1
for (let i = 0; i < M.length; i++) {
r = M[i]
max1.push(Math.max(...r))
min1.push(Math.min(...r))
}
// Initialise res to 0
res = 0
// Multiply and add both array
for (let i = 0; i < N; i++)
res += (max1[i] * min1[i])
// Return res
return res
}
// Driver code
// Original matrix
let M = [[3, 2, 5],
[7, 5, 4],
[7, 2, 9]]
// N size of matrix
let N = M.length
// Call matOne function for rows
let R = matOne(M, N)
// Transpose the matrix
T = transpose(M, N)
// Call matOne function for column
C = matOne(T, N)
// Print the absolute difference
document.write(Math.abs(R - C))
// This code is contributed by Potta Lokesh
</script>
Producción:
11
Tiempo Complejidad :O(N 2 log(N))
Espacio Auxiliar :O(1)
Publicación traducida automáticamente
Artículo escrito por harshdeepmahajan88 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA