หาตัวเลขร่วมในทุกแถวของเมทริกซ์ที่เรียงแล้วใน C++

โจทย์

ให้เมทริกซ์ที่แต่ละแถวเรียงจากน้อยไปมาก ต้องการหาตัวเลขที่ปรากฏในทุกแถว

ตัวอย่าง: เมทริกซ์ 4x5 ตัวเลขร่วมคือ 5

วิธีแก้ปัญหา (Hash)

1. สร้าง unordered_map นับความถี่ของแต่ละตัวเลขในแต่ละแถว (นับแค่ครั้งแรกในแต่ละแถว)
2. ลูปหาตัวเลขที่มีความถี่เท่ากับจำนวนแถว (M)

วิธีนี้ใช้ได้แม้แถวจะไม่เรียงลำดับ

ตัวอย่างโค้ด C++

#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;
    for (int i = 0; i < M; i++) {
        count[matrix[i][0]]++;
        for (int 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;
}

ผลลัพธ์

Common element is 5