ค้นหาองค์ประกอบที่แตกต่างซึ่งพบได้ทั่วไปในแถวทั้งหมดของเมทริกซ์ใน C++

แนวคิด

ด้วยความเคารพต่อเมทริกซ์ขนาด m x m ที่กำหนด ปัญหาคือการกำหนดองค์ประกอบที่แตกต่างกันทั้งหมดซึ่งพบได้ทั่วไปในแถวทั้งหมดของเมทริกซ์ จึงสามารถแสดงองค์ประกอบในลำดับใดก็ได้

อินพุต

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

วิธีการ

วิธีแรก:ใช้ลูปที่ซ้อนกันสามลูป ตรวจสอบว่าองค์ประกอบของแถวที่ 1 มีอยู่ในแถวที่ตามมาทั้งหมดหรือไม่ ที่นี่เวลาความซับซ้อนคือ O(m^3) อาจต้องใช้พื้นที่เพิ่มเติมเพื่อควบคุมองค์ประกอบที่ซ้ำกัน

วิธีที่สอง:จัดเรียงหรือจัดเรียงแถวทั้งหมดของเมทริกซ์ทีละรายการตามลำดับที่เพิ่มขึ้น ดังนั้นเราจึงใช้แนวทางแก้ไขของปัญหาในการกำหนดองค์ประกอบทั่วไปใน 3 อาร์เรย์ที่จัดเรียง มีการดำเนินการตามแบบเดียวกัน

ตัวอย่าง

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

ผลลัพธ์

2 4 15