Tìm các phần tử khác nhau chung cho tất cả hàng của ma trận trong C++

Khái niệm

Cho ma trận m x m, tìm tất cả các phần tử khác nhau chung cho tất cả các hàng của ma trận. Các phần tử có thể in 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 1: Ba vòng lặp lồng nhau. Kiểm tra phần tử hàng 1 có mặt ở tất cả các hàng sau. Độ phức tạp O(m^3). Cần không gian thêm để xử lý trùng lặp.

Phương pháp 2: Sắp xếp từng hàng của ma trận theo thứ tự tăng dần. Sau đó áp dụng phương pháp biến đổi của bài toán tìm phần tử chung trong 3 mảng đã sắp xếp.

Ví dụ

// C++ tìm phần tử khác nhau chung cho tất cả hàng ma trận
#include <bits/stdc++.h>
using namespace std;
const int MAX1 = 100;

void sortRows1(int mat1[][MAX1], int m){
    for (int i=0; i<m; i++)
        sort(mat1[i], mat1[i] + m);
}

void findAndPrintCommonElements1(int mat1[][MAX1], int m){
    sortRows1(mat1, m);
    int curr_index1[m];
    memset(curr_index1, 0, sizeof(curr_index1));
    int f = 0;
    for (; curr_index1[0]<m; curr_index1[0]++){
        int value1 = mat1[0][curr_index1[0]];
        bool present1 = true;
        for (int i=1; i<m; i++){
            while (curr_index1[i] < m && mat1[i][curr_index1[i]] <= value1)
                curr_index1[i]++;
            if (mat1[i][curr_index1[i]-1] != value1)
                present1 = false;
            if (curr_index1[i] == m){
                f = 1;
                break;
            }
        }
        if (present1)
            cout << value1 << " ";
        if (f == 1)
            break;
    }
}

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