钟表-yiteyi-C++库

给定一个m×n矩阵，求O（mn）时间内所有行中的所有公共元素，并遍历一次矩阵。 例子：

null

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 18 and 1 are present in all rows.

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 简单解决方案 是考虑每个元素并检查它是否存在于所有行中。如果有，就打印出来。 A. 更好的解决方案 就是对矩阵中的所有行进行排序，并使用类似的方法在这里 .排序需要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;                       
           
                                                 // initialize 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 && mp[mat[i][j]]==M)                       
                                                 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<>();                       
                                   
                                                 // initialize 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                                     ()                       
           
                                                 # initialize 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                                     >();                       
                                   
                                                 // initialize 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                       

Javascript

                         <script>                       
                         // Javascript Program to prints common element in all                       
                         // rows of matrix                       
                                   
                                                 // Specify number of rows and columns                       
                                                 let M = 4;                       
                                                 let N =5;                       
                                   
                                                 // prints common element in all rows of matrix                       
                                                 function                                     printCommonElements(mat)                       
                                                 {                       
                                                 let mp =                                     new                                     Map();                       
                                   
                                                 // initialize 1st row elements with value 1                       
                                                 for                                     (let j = 0; j < N; j++)                       
                                                 mp.set(mat[0][j],1);                       
                                   
                                                 // traverse the matrix                       
                                                 for                                     (let i = 1; i < M; i++)                       
                                                 {                       
                                                 for                                     (let 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.set(mat[i][j], i + 1);                       
                                   
                                                 // If this is last row                       
                                                 if                                     (i == M - 1)                       
                                                 document.write(mat[i][j] +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 let 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 unknown2108                       
                         </script>                       

输出：

8 1

这个解的时间复杂度是O（m*n），我们只对矩阵进行一次遍历。本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章