# 給定矩陣的所有行中的公共元素 > 原文： [https://www.geeksforgeeks.org/common-elements-in-all-rows-of-a-given-matrix/](https://www.geeksforgeeks.org/common-elements-in-all-rows-of-a-given-matrix/) 給定一個 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. ``` **簡單解決方案**是考慮每個元素，并檢查所有行中是否存在該元素。 如果存在，請打印。 **更好的解決方案**是對矩陣中的所有行進行排序，并使用與[在此處](https://www.geeksforgeeks.org/find-common-element-rows-row-wise-sorted-matrix/)類似的方法。 排序將花費 O（mnlogn）時間，而查找公用元素將花費 O（mn）時間。 因此，此解決方案的總體時間復雜度為 O（mnlogn） **我們能比 O（mnlogn）做得更好嗎？** 這個想法是使用地圖。 首先，我們將第一行的所有元素插入到地圖中。 對于剩余行中的所有其他元素，我們檢查其是否存在于地圖中。 如果它存在于地圖中并且在當前行中沒有重復，則我們將地圖中元素的計數增加 1，否則我們將忽略該元素。 如果當前遍歷的行是最后一行，則在元素出現 m-1 次之前，我們將對其進行打印。 以下是該想法的實現。 ## C++ ```cpp // 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; } ```