对于给定的mxm矩阵,问题在于确定矩阵所有行共有的所有不同元素。因此,元素可以按任何顺序显示。
mat[][] = { {13, 2, 15, 4, 17}, {15, 3, 2, 4, 36}, {15, 2, 15, 4, 12}, {15, 26, 4, 3, 2}, {2, 19, 4, 22, 15} }
输出结果
2 4 15
第一种方法:实现三个嵌套循环。验证第一行的元素是否存在于所有后续行中。在这里,时间复杂度为O(m ^ 3)。可能需要额外的空间来控制重复的元素。
第二种方法:以递增顺序分别排列或排序矩阵的所有行。因此,我们然后对确定3个排序数组中的公共元素的问题实施了改进的方法。下面给出了相同的实现。
// C++ implementation to find distinct elements //矩阵的所有行共有 #include <bits/stdc++.h> using namespace std; const int MAX1 = 100; //显示功能进行单独排序 //每行按升序排列 void sortRows1(int mat1[][MAX1], int m){ for (int i=0; i<m; i++) sort(mat1[i], mat1[i] + m); } //显示功能以查找所有常见元素 void findAndPrintCommonElements1(int mat1[][MAX1], int m){ //用于单独对行进行排序 sortRows1(mat1, m); //显示每行存储的当前列索引 //中搜索元素的位置 //那行 int curr_index1[m]; memset(curr_index1, 0, sizeof(curr_index1)); int f = 0; for (; curr_index1[0]<m; curr_index1[0]++){ //指示当前列索引处存在的值 //第一行 int value1 = mat1[0][curr_index1[0]]; bool present1 = true; //搜索“值” //后续行 for (int i=1; i<m; i++){ //所有元素 //当前列索引中的行 //直到元素大于“值” //找到或行的末尾是 //遇到 while (curr_index1[i] < m && mat1[i][curr_index1[i]] <= value1) curr_index1[i]++; //现在,如果该元素不在列中 //在该行的“ curr_index”之前 if (mat1[i][curr_index1[i]-1] != value1) present1 = false; //现在,如果该行的所有元素都具有 //被遍历 if (curr_index1[i] == m){ f = 1; break; } } //现在,如果“值”对于所有行都是公用的 if (present1) cout << value1 << " "; //现在,如果有任何行已被完全遍历 //那么就找不到更多的通用元素 if (f == 1) break; } } //测试上面的驱动程序 int main(){ int mat1[][MAX1] = { {13, 2, 15, 4, 17},{15, 3, 2, 4, 36},{15, 2, 15, 4, 12}, {15, 26, 4, 3, 2},{2, 19, 4, 22, 15}}; int m = 5; findAndPrintCommonElements1(mat1, m); return 0; }
输出结果
2 4 15