Tìm một phần tử chung trong tất cả các hàng của ma trận được sắp xếp theo hàng nhất định trong C ++

Giả sử chúng ta có một ma trận trong đó mỗi hàng được sắp xếp. Chúng ta phải viết một hàm tìm các phần tử chung trong mỗi hàng. Giả sử ma trận giống như bên dưới -

Kết quả sẽ là 5.

Để giải quyết điều này, chúng tôi sẽ sử dụng phương pháp dựa trên băm. Cách tiếp cận này cũng có thể được sử dụng khi các hàng không được sắp xếp. Chúng tôi phải làm theo một số bước để thực hiện việc này -

Chúng tôi sẽ tạo một bảng băm với tất cả các khóa là các phần tử riêng biệt của hai 1. Tất cả các giá trị sẽ là 0

lặp qua từng phần tử trong ma trận, nếu số có trong bảng băm thì tăng số đếm lên 1. Cuối cùng kiểm tra xem có giá trị nào đó mà số lượng của nó giống với số hàng của ma trận hay không. Nếu vậy thì điều đó có trong mỗi hàng. (Giả sử một giá trị không lặp lại trong một hàng)

Ví dụ

#include<iostream>
#include<unordered_map>
#define M 4
#define N 5
using namespace std;
int getCommonElement(int matrix[M][N]) {
   unordered_map<int, int> count;
   int i, j;
   for (i = 0; i < M; i++) {
      count[matrix[i][0]]++;
      for (j = 1; j < N; j++) {
         if (matrix[i][j] != matrix[i][j - 1])
         count[matrix[i][j]]++;
      }
   }
   for (auto ele : count) {
      if (ele.second == M)
      return ele.first;
   }
   return -1;
}
int main() {
   int matrix[M][N] = {
      { 1, 2, 3, 4, 5 },
      { 2, 4, 5, 8, 10 },
      { 3, 5, 7, 9, 11 },
      { 1, 3, 5, 7, 9 },
   };
   int result = getCommonElement(matrix);
   if (result == -1)
      cout << "No common element has found";
   else
      cout << "Common element is " << result;
}

Đầu ra

Common element is 5