หาจำนวน Positional Elements ในเมทริกซ์ด้วย C++

ภาพรวมปัญหา

ได้รับเมทริกซ์ mat[m][n] ต้องหาจำนวน "Positional Elements" ซึ่งคือองค์ประกอบที่เป็นค่าสูงสุดหรือต่ำสุดของแถวหรือคอลัมน์ที่มันอยู่

ตัวอย่าง

อินพุต

mat[][] = { {2, 5, 7},
            {1, 3, 4},
            {5, 1, 3} }

เอาต์พุต

8

คำอธิบาย

Positional Elements: 2, 5, 7, 1, 4, 5, 1, 3

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

1. หาค่า max และ min ของแต่ละแถว → เก็บใน rowmax[], rowmin[]
2. หาค่า max และ min ของแต่ละคอลัมน์ → เก็บใน colmax[], colmin[]
3. ตรวจสอบทุกเซลล์ ว่าเท่ากับ rowmax/rowmin/colmax/colmin ของตำแหน่งนั้นหรือไม่

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

#include <iostream>
using namespace std;

const int MAX = 100;

int countAllPositionalElements(int mat[][MAX], int m, int n) {
    int rowmax[m], rowmin[m];
    int colmax[n], colmin[n];
    
    // หา max/min ของแต่ละแถว
    for (int i = 0; i < m; i++) {
        int rminn = 10000, rmaxx = -10000;
        for (int j = 0; j < n; j++) {
            if (mat[i][j] > rmaxx) rmaxx = mat[i][j];
            if (mat[i][j] < rminn) rminn = mat[i][j];
        }
        rowmax[i] = rmaxx;
        rowmin[i] = rminn;
    }
    
    // หา max/min ของแต่ละคอลัมน์
    for (int j = 0; j < n; j++) {
        int cminn = 10000, cmaxx = -10000;
        for (int i = 0; i < m; i++) {
            if (mat[i][j] > cmaxx) cmaxx = mat[i][j];
            if (mat[i][j] < cminn) cminn = mat[i][j];
        }
        colmax[j] = cmaxx;
        colmin[j] = cminn;
    }
    
    // นับ positional elements
    int positionalCount = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (mat[i][j] == rowmax[i] || mat[i][j] == rowmin[i] ||
                mat[i][j] == colmax[j] || mat[i][j] == colmin[j]) {
                positionalCount++;
            }
        }
    }
    return positionalCount;
}

int main() {
    int mat[][MAX] = { {2, 5, 7}, {1, 3, 4}, {5, 1, 3} };
    int m = 3, n = 3;
    cout << "Number of positional elements is " << countAllPositionalElements(mat, m, n);
    return 0;
}

เอาต์พุต

Number of positional elements is 8

สรุป

Complexity: O(m×n) ใช้พื้นที่ O(m+n) สำหรับเก็บ max/min ของแถวและคอลัมน์