算法题：给定矩阵的所有行中的公共元素

2021年3月30日09:56:08 发表评论 1,081 次浏览

本文概述

C ++
Java
Python3
C#

给定一个m x n矩阵, 找出在O(mn)时间和矩阵的一个遍历中所有行中存在的所有公共元素。

例子：

Input:
mat[4][5] = {{1, 2, 1, 4, 8}, {3, 7, 8, 5, 1}, {8, 7, 7, 3, 1}, {8, 1, 2, 7, 9}, };

Output: 
1 8 or 8 1
8 and 1 are present in all rows.

一种简单的解决方案是要考虑每个元素, 并检查所有行中是否都存在该元素。如果存在, 则打印它。

一种更好的解决方案是对矩阵中的所有行进行排序, 并使用与上述类似的方法这里。排序将花费O(mnlogn)时间, 而查找公用元素将花费O(mn)时间。因此, 此解决方案的总体时间复杂度为O(mnlogn)

我们可以做得比O(mnlogn)好吗？

这个想法是使用地图。首先, 我们将第一行的所有元素插入到地图中。对于剩余行中的所有其他元素, 我们检查其是否存在于地图中。如果它存在于地图中并且在当前行中没有重复, 则将地图中元素的计数增加1, 否则我们将忽略该元素。如果当前遍历的行是最后一行, 则如果元素出现过m-1次, 则我们将其打印。

以下是该想法的实现。

C ++

// A Program to prints common element in all
// rows of matrix
#include <bits/stdc++.h>
using namespace std;
  
// Specify number of rows and columns
#define M 4
#define N 5
  
// prints common element in all rows of matrix
void printCommonElements( int mat[M][N])
{
     unordered_map< int , int > mp;
  
     // initalize 1st row elements with value 1
     for ( int j = 0; j < N; j++)
         mp[mat[0][j]] = 1;
  
     // traverse the matrix
     for ( int i = 1; i < M; i++)
     {
         for ( int j = 0; j < N; j++)
         {
             // If element is present in the map and
             // is not duplicated in current row.
             if (mp[mat[i][j]] == i)
             {
                // we increment count of the element
                // in map by 1
                 mp[mat[i][j]] = i + 1;
  
                 // If this is last row
                 if (i==M-1)
                   cout << mat[i][j] << " " ;
             }
         }
     }
}
  
// driver program to test above function
int main()
{
     int mat[M][N] =
     {
         {1, 2, 1, 4, 8}, {3, 7, 8, 5, 1}, {8, 7, 7, 3, 1}, {8, 1, 2, 7, 9}, };
  
     printCommonElements(mat);
  
     return 0;
}

Java

// Java Program to prints common element in all
// rows of matrix
import java.util.*;
  
class GFG 
{
  
// Specify number of rows and columns
static int M = 4 ;
static int N = 5 ;
  
// prints common element in all rows of matrix
static void printCommonElements( int mat[][])
{
  
     Map<Integer, Integer> mp = new HashMap<>();
      
     // initalize 1st row elements with value 1
     for ( int j = 0 ; j < N; j++)
         mp.put(mat[ 0 ][j], 1 );
          
     // traverse the matrix
     for ( int i = 1 ; i < M; i++)
     {
         for ( int j = 0 ; j < N; j++)
         {
             // If element is present in the map and
             // is not duplicated in current row.
             if (mp.get(mat[i][j]) != null && mp.get(mat[i][j]) == i)
             {
                 // we increment count of the element
                 // in map by 1
                 mp.put(mat[i][j], i + 1 );
  
                 // If this is last row
                 if (i == M - 1 )
                     System.out.print(mat[i][j] + " " );
             }
         }
     }
}
  
// Driver code
public static void main(String[] args) 
{
     int mat[][] =
     {
         { 1 , 2 , 1 , 4 , 8 }, { 3 , 7 , 8 , 5 , 1 }, { 8 , 7 , 7 , 3 , 1 }, { 8 , 1 , 2 , 7 , 9 }, };
  
     printCommonElements(mat);
}
}
  
// This code contributed by Rajput-Ji

Python3

# A Program to prints common element 
# in all rows of matrix
  
# Specify number of rows and columns
M = 4
N = 5
  
# prints common element in all 
# rows of matrix
def printCommonElements(mat):
  
     mp = dict ()
  
     # initalize 1st row elements 
     # with value 1
     for j in range (N):
         mp[mat[ 0 ][j]] = 1
  
     # traverse the matrix
     for i in range ( 1 , M):
         for j in range (N):
              
             # If element is present in the
             # map and is not duplicated in 
             # current row.
             if (mat[i][j] in mp.keys() and
                              mp[mat[i][j]] = = i):
                                   
             # we increment count of the 
             # element in map by 1
                 mp[mat[i][j]] = i + 1
  
                 # If this is last row
                 if i = = M - 1 :
                     print (mat[i][j], end = " " )
              
# Driver Code
mat = [[ 1 , 2 , 1 , 4 , 8 ], [ 3 , 7 , 8 , 5 , 1 ], [ 8 , 7 , 7 , 3 , 1 ], [ 8 , 1 , 2 , 7 , 9 ]]
  
printCommonElements(mat)
  
# This code is conteibuted 
# by mohit kumar 29

C#

// C# Program to print common element in all
// rows of matrix to another.
using System; 
using System.Collections.Generic; 
  
class GFG 
{
  
// Specify number of rows and columns
static int M = 4;
static int N = 5;
  
// prints common element in all rows of matrix
static void printCommonElements( int [, ]mat)
{
  
     Dictionary< int , int > mp = new Dictionary< int , int >();
      
     // initalize 1st row elements with value 1
     for ( int j = 0; j < N; j++)
     {
         if (!mp.ContainsKey(mat[0, j]))
             mp.Add(mat[0, j], 1);
     }
      
     // traverse the matrix
     for ( int i = 1; i < M; i++)
     {
         for ( int j = 0; j < N; j++)
         {
             // If element is present in the map and
             // is not duplicated in current row.
             if (mp.ContainsKey(mat[i, j])&&
                (mp[mat[i, j]] != 0 && 
                 mp[mat[i, j]] == i))
             {
                 // we increment count of the element
                 // in map by 1
                 if (mp.ContainsKey(mat[i, j]))
                 {
                     var v = mp[mat[i, j]];
                     mp.Remove(mat[i, j]);
                     mp.Add(mat[i, j], i + 1);
                 }
                 else
                     mp.Add(mat[i, j], i + 1);
  
                 // If this is last row
                 if (i == M - 1)
                     Console.Write(mat[i, j] + " " );
             }
         }
     }
}
  
// Driver code
public static void Main(String[] args) 
{
     int [, ]mat = {{1, 2, 1, 4, 8}, {3, 7, 8, 5, 1}, {8, 7, 7, 3, 1}, {8, 1, 2, 7, 9}};
  
     printCommonElements(mat);
}
}
  
// This code is contributed by 29AjayKumar

输出如下：