Random Flip Matrix สุ่มพลิกเมทริกซ์ใน C++

มีเมทริกซ์ไบนารี n_rows × n_cols เริ่มต้นเป็น 0 ทั้งหมด เขียนฟังก์ชัน flip() สุ่มเลือก 0 หนึ่งช่อง เปลี่ยนเป็น 1 คืนตำแหน่ง [row,col] และ reset() รีเซ็ตทั้งหมดเป็น 0

เพิ่มประสิทธิภาพ: ลดการเรียก random(), ปรับเวลาและพื้นที่

วิธีแก้ปัญหา (Hash Map + Virtual Array)

1. เก็บ map holes สำหรับ index ที่ถูก flip แล้ว
2. initializer: n, m, size = n*m
3. flip():
   • id = rand() % size, size--
   • rid = id
   • ถ้า id ใน holes: id = holes[id]
   • holes[rid] = holes[size] ถ้ามี มิฉะนั้น size
   • คืน {id/m, id%m}
4. reset(): size = n*m, clear holes

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

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

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    unordered_map<int, int> holes;
    int n, m, size;
    
    Solution(int n_rows, int n_cols) {
        srand(time(NULL));
        n = n_rows; m = n_cols; size = n * m;
    }
    
    vector<int> flip() {
        int id = rand() % size;
        size--;
        int rid = id;
        if (holes.count(id)) id = holes[id];
        holes[rid] = holes.count(size) ? holes[size] : size;
        return {id / m, id % m};
    }
    
    void reset() {
        size = n * m;
        holes.clear();
    }
};

int main() {
    Solution ob(2, 2);
    for (int i = 0; i < 4; i++) print_vector(ob.flip());
    return 0;
}

Input

Initialize constructor 2,2 and call flip four times

Output

[1, 1, ] [0, 0, ] [1, 0, ] [0, 1, ]