Đếm phần tử mảng xuất hiện trên mỗi hàng ma trận trong C++

Giới thiệu

Cho mảng 1D và ma trận 2D. Với mỗi hàng của ma trận, đếm số phần tử của mảng 1D xuất hiện trên hàng đó.

Ví dụ

arr = [2,4,6], matrix = [[2,4,6], [3,4,6], [6,2,1]]

• Hàng 1: 3 phần tử (2,4,6)
• Hàng 2: 2 phần tử (4,6)
• Hàng 3: 2 phần tử (6,2)

Các cách tiếp cận

Cách 1: Naive O(rows × cols × arr_size)

Ba vòng lặp lồng nhau kiểm tra từng phần tử.

Cách 2: Hiệu quả O(rows × (cols + arr_size)) dùng unordered_set

Với mỗi hàng, đưa các phần tử vào unordered_set, sau đó kiểm tra từng phần tử của mảng 1D.

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

#define ROW 3
#define COL 3

// Cách 1: Naive
void countNaive(int matrix[ROW][COL], int arr[], int size) {
    for (int i = 0; i < ROW; i++) {
        int count = 0;
        for (int k = 0; k < size; k++) {
            for (int j = 0; j < COL; j++) {
                if (arr[k] == matrix[i][j]) {
                    count++;
                    break;
                }
            }
        }
        cout << "Hang " << i+1 << ": " << count << endl;
    }
}

// Cách 2: Hiệu quả với unordered_set
void countEfficient(int matrix[ROW][COL], int arr[], int size) {
    for (int i = 0; i < ROW; i++) {
        unordered_set<int> rowSet;
        for (int j = 0; j < COL; j++)
            rowSet.insert(matrix[i][j]);
        
        int count = 0;
        for (int k = 0; k < size; k++)
            if (rowSet.count(arr[k])) count++;
        
        cout << "Hang " << i+1 << ": " << count << endl;
    }
}

int main() {
    int matrix[ROW][COL] = {{2,4,6}, {3,4,6}, {6,2,1}};
    int arr[] = {2, 4, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Cach hieu qua:\n";
    countEfficient(matrix, arr, size);
    return 0;
}

Đầu vào

arr=[2,4,6], matrix=[[2,4,6],[3,4,6],[6,2,1]]

Đầu ra

Hang 1: 3
Hang 2: 2
Hang 3: 2