519 随机翻转矩阵（二维-＞一维）

一时失言乱红尘 2022-08-30 04:23 150阅读 0赞

**1. 问题描述：**

题中给出一个 n\_rows 行 n\_cols 列的二维矩阵，且所有值被初始化为 0。要求编写一个 flip 函数，均匀随机的将矩阵中的 0 变为 1，并返回该值的位置下标 \[row\_id,col\_id\]；同样编写一个 reset 函数，将所有的值都重新置为 0。尽量最少调用随机函数 Math.random()，并且优化时间和空间复杂度。

**注意:**  
1 <= n\_rows, n\_cols <= 10000  
0 <= row.id < n\_rows 并且 0 <= col.id < n\_cols  
当矩阵中没有值为 0 时，不可以调用 flip 函数  
调用 flip 和 reset 函数的次数加起来不会超过 1000 次

**示例 1：**

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

**示例 2：**

输入:  
\["Solution","flip","flip","reset","flip"\]  
\[\[1,2\],\[\],\[\],\[\],\[\]\]  
输出: \[null,\[0,0\],\[0,1\],null,\[0,0\]\]  
输入语法解释：  
输入包含两个列表：被调用的子程序和他们的参数。Solution 的构造函数有两个参数，分别为 n\_rows 和 n\_cols。flip 和 reset 没有参数，参数总会以列表形式给出，哪怕该列表为空  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/random-flip-matrix

**2. 思路分析：**

分析题目可以知道最主要的操作是均匀随机地将二维矩阵中为0的元素变为1，所以这是一个二维的问题，首先我们需要将二维的问题转换为一维的问题，这里可以将二维矩阵的横坐标与纵坐标映射为一维数组中的坐标，这样就转换为了一维的问题，这样问题就转化为在一维数组中随机选出一个值为0的元素将其删除，在删除元素的时候我们可以采用这样的策略，我们可以将数组末尾的元素覆盖到当前要删除元素的位置，然后删除最后一个元素即可，这样就可以保证删除之后的值为0的元素都是连续的。并且一开始的时候整个数组都是连续的，所以每个数组对应的下标对应的值都是当前的下标，所以我们可以使用哈希表来记录那些特殊的位置，也即下标对应的值不是当前的下标的情况，这样当哈希表中存在值的时候说明当前位置的值不是当前的下标，如果不存在的话那么默认对应自己的下标，这样就可以节省一定的空间。

**3. 代码如下：**

from typing import List
    import random
    
    
    class Solution:
        r, c, k, dic = 0, 0, 0, None
    
        def __init__(self, n_rows: int, n_cols: int):
            self.r, self.c = n_rows, n_cols
            # k为当前剩余元素为0的数目
            self.k = n_rows * n_cols
            self.dic = dict()
    
        def flip(self) -> List[int]:
            r, c, k = self.r, self.c, self.k
            dic = self.dic
            # 生成0~k-1的随机数
            x = random.randint(0, k - 1)
            y = x
            # 当前的x在哈希表中存在说明当前的位置应该是哈希表中的值
            if x in dic:
                y = dic[x]
            # 判断最后一个数字是否存在
            if k - 1 in dic:
                dic[x] = dic[k - 1]
                del dic[k - 1]
            else:
                dic[x] = k - 1
            self.k -= 1
            # 将二维坐标映射为一维坐标
            return [y // c, y % c]
    
        def reset(self) -> None:
            dic = self.dic
            # 清空字典值
            dic.clear()
            self.k = self.r * self.c