Computer >> Máy Tính >  >> Lập trình >> C ++

Tìm phần tử chung nhỏ nhất trong tất cả các hàng trong C ++

Giả sử chúng ta có một mat ma trận trong đó mọi hàng được sắp xếp theo thứ tự không giảm, chúng ta phải tìm phần tử chung nhỏ nhất trong tất cả các hàng. Nếu không có phần tử chung, thì trả về -1. Vì vậy, nếu ma trận giống như -

1 2 3 4 5
2 4 5 8 10
3 5 7 9 11
1 3 5 7 9

Đầu ra sẽ là 5

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định một ánh xạ m, n:=số hàng của ma trận,

  • nếu n không phải là 0, thì x =kích thước cột, nếu không thì 0

  • cho tôi trong phạm vi từ 0 đến n - 1

    • cho j trong phạm vi 0 đến x - 1

      • nếu m [mat [i, j]] + 1 =i + 1, thì tăng m [mat [i, j]] lên 1

  • cho mỗi cặp khóa-giá trị i

    • nếu giá trị của tôi là n, thì trả về khóa của tôi

  • trả về -1

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int smallestCommonElement(vector<vector<int>>& mat) {
      map <int, int> m;
      int n = mat.size();
      int x = n? mat[0].size() : 0;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < x; j++){
            if(m[mat[i][j]] + 1 == i + 1){
               m[mat[i][j]]++;
            }
         }
      }
      map <int, int> :: iterator it = m.begin();
      while(it != m.end()){
         if(it->second == n){
            return it->first;
         }
         it++;
      }
      return -1;
   }
};
main(){
   vector<vector<int>> v = {{1,2,3,4,5},{2,4,5,8,10},{3,5,7,9,11},{1,3,5,7,9}};
   Solution ob;
   cout << (ob.smallestCommonElement(v));
}

Đầu vào 

[[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]

Đầu ra 

5