เซลล์ที่มีค่าคี่ในเมทริกซ์ใน C++

ปัญหา

ได้รับ n, m ขนาดเมทริกซ์ เริ่มต้นเป็น 0 ทั้งหมด มี Indices indices[i] = [ri, ci] สำหรับแต่ละคู่ ให้เพิ่มทุกเซลล์ในแถว ri และคอลัมน์ ci ขึ้น 1 หาจำนวนเซลล์ที่มีค่าคี่หลังปรับค่าทุก indices

วิธีแก้

• odd = 0, x = จำนวนแถวของ indices
• สร้างเมทริกซ์ mat
• ลูปแต่ละ index: เพิ่มแถว ri และคอลัมน์ ci
• นับเซลล์คี่: odd += mat[i][j] & 1

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

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

class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& in) {
        int odd = 0;
        int x = in.size();
        vector<vector<int>> mat(n, vector<int>(m));
        for (int i = 0; i < x; i++) {
            int r = in[i][0];
            int c = in[i][1];
            for (int j = 0; j < m; j++) mat[r][j]++;
            for (int j = 0; j < n; j++) mat[j][c]++;
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) odd += mat[i][j] & 1;
        return odd;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> c = {{0,1}, {1,1}};
    cout << ob.oddCells(2, 3, c);
}

อินพุต

2 3 {{0,1},{1,1}}

เอาต์พุต

6

คำอธิบาย

เมทริกซ์ 2×3 เริ่มต้นเป็น 0

Index [0,1]: เพิ่มแถว 0 และคอลัมน์ 1

Index [1,1]: เพิ่มแถว 1 และคอลัมน์ 1

ผลลัพธ์เซลล์คี่ = 6 เซลล์

เพิ่มประสิทธิภาพได้: ไม่ต้องสร้างเมทริกซ์เต็ม ใช้ Array นับแถวและคอลัมน์แยกกัน