在C ++中查找矩阵所有行共有的不同元素

概念

对于给定的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