欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode519. 随机翻转矩阵

程序员文章站 2022-07-10 19:52:28
因为n_rows和n_cols最大能到104,所以不能开二维数组,因为那样空间复杂度回到108。题目说了调用flip和reset的次数加起来不会超过1000次,所以矩阵是比较稀疏的,我们只需要记录所有1的位置即可。我们可以用一个哈希表记录所有1的位置。为了方便,我们把二维的位置映射到一个int变量,哈希表中只记录这个int变量,比如,如果位置是第r行第c列,那么我们得到:pos = r * cols + c,其中cols是二维矩阵的列数(即n_cols), pos是将{r, c}映射到一维空间的下标....

LeetCode519. 随机翻转矩阵

因为n_rows和n_cols最大能到104,所以不能开二维数组,因为那样空间复杂度回到108。

题目说了调用flip和reset的次数加起来不会超过1000次,所以矩阵是比较稀疏的,我们只需要记录所有1的位置即可。
我们可以用一个哈希表记录所有1的位置。为了方便,我们把二维的位置映射到一个int变量,哈希表中只记录这个int变量,
比如,如果位置是第r行第c列,那么我们得到:pos = r * cols + c,其中cols是二维矩阵的列数(即n_cols), pos是将{r, c}映射到一维空间的下标。

随机翻转一个0为1的时候,我们只要找出一个不为1(即哈希表中没记录过的)位置pos = rand() % capacity,将这个位置记录到哈希表中(其中capacity是矩阵的大小,即n_rows * n_cols),
并且求出这个位置对应的二维矩阵的行号: r = pos / cols, 列号: c = pos % cols,将{r, c}作为filp()函数的返回值即可。

reset()方法只需要将哈希表clear即可,表示当前没有记录矩阵中的任何位置的值为1。

代码如下:

using LL = long long;

class Solution {
public:
    unordered_set<LL> hash;            // 哈希表,记录矩阵中的位置映射到一维空间的下标
    LL rows, cols, capacity;           // 行数、列数、矩阵的大小

    Solution(int n_rows, int n_cols) {
        rows = n_rows;
        cols = n_cols;
        capacity = rows * cols;
    }
    
    vector<int> flip() {
        LL r, c, pos;
        do {
            pos = rand() % capacity;            // 随机得到一个pos
        } while(hash.count(pos) != 0);
        hash.insert(pos);
        r = pos / cols;                         // pos对应的二维矩阵中的行号r是pos / cols
        c = pos % cols;                         // pos对应的二维矩阵中的列号c是pos % cols
        return {(int)r, (int)c};
    }
    
    void reset() {
        hash.clear();                           // 清空哈希表
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(n_rows, n_cols);
 * vector<int> param_1 = obj->flip();
 * obj->reset();
 */

本文地址:https://blog.csdn.net/RJ_theMag/article/details/109638199

相关标签: LeetCode