Найдите абсолютную разницу между произведением минимума и максимума по строкам и столбцам в заданной матрице

Опубликовано: 20 Сентября, 2022

Учитывая квадратную матрицу M[][] размера N x N , задача состоит в том, чтобы найти максимумы и минимумы каждой из строк и столбцов , умножить соответствующие максимумы и минимумы каждой строки на таковые в каждом столбце. Наконец, вернуть абсолютная разница обоих из них.

Примеры :

Input: M[][] = [ [ 3, 2, 5 ], [ 7, 5, 4 ], [ 7, 2, 9 ] ]
Output: 11
Explanation:
Input: M = [ [1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
Output: 40

Наивный подход: задача может быть решена путем моделирования заданных операций. Выполните следующие шаги, чтобы решить проблему:

Возьмите 2 массива max1[] и min1[] для хранения максимума и минимума каждой строки или каждого столбца.
Сначала сохраните максимум каждой строки в max1[ ] и минимум каждой строки в min1[ ] .
Множественное разрешение матрицы и возврата, сохраните его в R .
Транспонируем матрицу M[ ] .
Затем сохраните максимум каждого столбца в max1[ ] и минимум каждого столбца в min1[ ] .
Умножьте обе матрицы и верните res, сохраните его в C .
Выведите абсолютную разницу R и C .

Ниже приведена реализация вышеуказанного подхода:

Сложность времени : НА)
Вспомогательное пространство : НА)

Подход, оптимизированный по пространству: этот подход аналогичен подходу 1, но в нем вспомогательное пространство будет оптимизировано без использования массивов max1 и min1. При этом направьте несколько, добавьте элемент и верните его.

Ниже приведена реализация вышеуказанного подхода:

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>

Сложность времени : НА)
Вспомогательное пространство : О(1)

Mathematical

Найдите абсолютную разницу между произведением минимума и максимума по строкам и столбцам в заданной матрице

C++

Java

Python3

C#

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ