leetcode-519-随机翻转矩阵

随机翻转矩阵

题面

leetcode题目

给你一个 \(m \times n\) 的二元矩阵 \(matrix\) ，且所有值被初始化为 \(0\) 。请你设计一个算法，随机选取一个满足 \(matrix[i][j] == 0\) 的下标 \((i, j)\) ，并将它的值变为 \(1\) 。所有满足 \(matrix[i][j] == 0\) 的下标 \((i, j)\) 被选取的概率应当均等。

尽量最少调用内置的随机函数，并且优化时间和空间复杂度。

实现 Solution 类：

• Solution(int m, int n) 使用二元矩阵的大小 m 和 n 初始化该对象
  
• int[] flip() 返回一个满足 matrix[i][j] == 0 的随机下标 [i, j] ，并将其对应格子中的值变为 1
  
• void reset() 将矩阵中所有的值重置为 0

example

输入
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
输出
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

解释
Solution solution = new Solution(3, 1);
solution.flip(); // 返回 [1, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
solution.flip(); // 返回 [2, 0]，因为 [1,0] 已经返回过了，此时返回 [2,0] 和 [0,0] 的概率应当相同
solution.flip(); // 返回 [0, 0]，根据前面已经返回过的下标，此时只能返回 [0,0]
solution.reset(); // 所有值都重置为 0 ，并可以再次选择下标返回
solution.flip(); // 返回 [2, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同

数据范围

• \(1 \leq m, n \leq 10^4\)
• 每次调用flip 时，矩阵中至少存在一个值为 \(0\) 的格子。
• 最多调用 \(1000\) 次 \(flip\) 和 \(reset\) 方法。

题解

总体思路

这里只需要把0变1，所以我们实际上是不关心矩阵具体的值的。很显然，我们可以参考之前翻转数组的思路，将矩阵一维化，从\((0,0)\)开始到\((m,n)\)为止依次命名为\(0,1,2,\cdots m\times n\)点，而对于点\(Point = a\)我们可以反推出其坐标为\(x = a/m\)，\(y = a%m\)。
到这，我们可以很显然的参考之前的思路，只需要翻转所有点数组即可，为了实现reset，很显然的我们需要对原始数组进行清空操作。我们观察数据范围，这一做法的最劣情况会进行\(10^4 \times 10^4 \times 10^3\)次操作，会TLE。
我们来考虑优化，注意到进行操作的次数中绝大部分浪费在了reset上，而我们又是不需要关心矩阵具体的值的，也就是说实际上整个矩阵，除了极少数被抽中的点为\(1\)外，都是\(0\)，对于稀疏矩阵，我们可以考虑使用哈希表存储所有的值为\(1\)的点，而不去计算所有的点即可。由于最多只会进行\(10^3\)次flip操作，则reset的最大代价为\(10^3\)。

代码

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <unordered_map>
using namespace std;
#define _DEBUG
class Solution
{
public:
    int matrixM;
    int matrixN;
    //int *matrixPoint;
    //vector<int> matrixPoint;
    unordered_map<int, int> matrixPoint;
    int size;
    int convertToPointX(int num)
    {
        return num % matrixM;
    }
    int convertToPointY(int num)
    {
        return num / matrixM;
    }

    void reInit(int num)
    {
        matrixPoint.clear();
        size = num;
    }
    void swap(int i, int j)
    {
        if (matrixPoint.count(i) == 0)
        {
            matrixPoint[i] = i;
        }
        if (matrixPoint.count(j) == 0)
        {
            matrixPoint[j] = j;
        }
        int temp = matrixPoint[i];
        matrixPoint[i] = matrixPoint[j];
        matrixPoint[j] = temp;
    }

    Solution(int m, int n)
    {
        matrixM = m;
        matrixN = n;
        srand(time(NULL));
        reInit(m * n);
    }

    vector<int> flip()
    {
        int idx = rand() % size;
        int rd = matrixPoint[idx];
        if (rd == 0)
        {
            rd = idx;
        }

        swap(size - 1, idx);
        size--;
        int x = convertToPointX(rd);
        int y = convertToPointY(rd);
        return vector<int>{x, y};
    }

    void reset()
    {
        reInit(matrixM * matrixN);
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(m, n);
 * vector<int> param_1 = obj->flip();
 * obj->reset();
 */
// for test
int main()
{
    Solution s(3, 1);
    auto x1 = s.flip();
    auto x2 = s.flip();
    auto x3 = s.flip();
    s.reset();
    auto x4 = s.flip();
    cout << x1[0] << " " << x1[1] << endl;
    cout << x2[0] << " " << x2[1] << endl;
    cout << x3[0] << " " << x3[1] << endl;
    cout << x4[0] << " " << x4[1] << endl;

    return 0;
}