Tìm các phần tử riêng biệt chung cho tất cả các hàng của Ma trận trong C ++

Khái niệm

Đối với một ma trận m x m cho trước, vấn đề là xác định tất cả các phần tử riêng biệt chung cho tất cả các hàng của ma trận. Vì vậy, các phần tử có thể được hiển thị theo bất kỳ thứ tự nào.

Đầu vào

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}
}

Đầu ra

2 4 15

Phương pháp

Phương pháp đầu tiên:Thực hiện ba vòng lặp lồng nhau. Xác minh xem một phần tử của hàng đầu tiên có trong tất cả các hàng tiếp theo hay không. Ở đây, Độ phức tạp thời gian là O (m ^ 3). Có thể cần thêm không gian để kiểm soát các phần tử trùng lặp.

Phương pháp thứ hai:Sắp xếp hoặc sắp xếp tất cả các hàng của ma trận riêng lẻ theo thứ tự tăng dần. Vì vậy, sau đó chúng tôi thực hiện một cách tiếp cận sửa đổi của bài toán xác định các phần tử chung trong 3 mảng đã sắp xếp. Sau một triển khai cho cùng một được đưa ra.

Ví dụ

// C++ implementation to find distinct elements
// common to all rows of a matrix
#include <bits/stdc++.h>
using namespace std;
const int MAX1 = 100;
// Shows function to individually sort
// each row in increasing order
void sortRows1(int mat1[][MAX1], int m){
   for (int i=0; i<m; i++)
   sort(mat1[i], mat1[i] + m);
}
// Shows function to find all the common elements
void findAndPrintCommonElements1(int mat1[][MAX1], int m){
   //Used to sort rows individually
   sortRows1(mat1, m);
   // Shows current column index of each row is stored
   // from where the element is being searched in
   // that row
   int curr_index1[m];
   memset(curr_index1, 0, sizeof(curr_index1));
   int f = 0;
   for (; curr_index1[0]<m; curr_index1[0]++){
      //Indicates value present at the current column index
      // of 1st row
      int value1 = mat1[0][curr_index1[0]];
      bool present1 = true;
      //Indicates 'value' is being searched in all the
      // subsequent rows
   for (int i=1; i<m; i++){
      // Used to iterate through all the elements of
      // the row from its current column index
      // till an element greater than the 'value'
      // is found or the end of the row is
      // encountered
      while (curr_index1[i] < m &&
      mat1[i][curr_index1[i]] <= value1)
      curr_index1[i]++;
      // Now if the element was not present at the column
      // before to the 'curr_index' of the row
      if (mat1[i][curr_index1[i]-1] != value1)
         present1 = false;
      // Now if all elements of the row have
      // been traversed
      if (curr_index1[i] == m){
         f = 1;
         break;
      }
   }
   // Now if the 'value' is common to all the rows
   if (present1)
      cout << value1 << " ";
   // Now if any row have been completely traversed
   // then no more common elements can be found
   if (f == 1)
      break;
   }
}
// Driver program to test above
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;
}

Đầu ra

2 4 15