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 ma trận mat 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, trả về -1. Ví dụ, ma trận:

Kết quả là 5.

Để giải quyết, chúng ta làm theo các bước:

• Định nghĩa map m, n := số hàng của ma trận.

• Nếu n != 0, x = số cột, ngược lại 0.

• Với i từ 0 đến n-1:

  • Với j từ 0 đến x-1:

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

• Duyệt qua các cặp khóa-giá trị trong m: nếu giá trị == n, trả về khóa.

• Trả về -1.

Ví dụ (C++)

Hãy xem 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;
    }
};

int 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