[LeetCode][519. 随机翻转矩阵] 2种方法:暴力法 和 降维 + 哈希表

By Long Luo

Leetcode 519. 随机翻转矩阵 题目如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
519. 随机翻转矩阵

给你一个m x 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

示例:
输入
["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 <= m, n <= 10^4
每次调用flip 时,矩阵中至少存在一个值为0的格子。
最多调用1000次flip和reset方法。

这道题和 384. 打乱数组 类似,考察的都是随机数的有用,下面我们用暴力法哈希表 22 种方法来解决这个问题。

方法一:暴力 + 随机数

思路与算法:

首先就想到的是新建一个矩阵 matrix\textit{matrix},调用 reset()\texttt{reset()} 时重置 matrix\textit{matrix}

但是调用 flip()\texttt{flip()} 呢?

  1. 生成一个 00total\textit{total} 的随机数 seed\textit{seed}
  2. 如果当前数组元素值为 11,说明已经被调用过,需要重新生成一个随机数,返回上一步;
  3. 如果当前数组元素值为 00,对其置 11,返回当前位置。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
int[][] matrix;
int row;
int col;
int total;
Random random = new Random();

public Solution(int m, int n) {
matrix = new int[m][n];
row = m;
col = n;
total = row * col;
}

public int[] flip() {
int rand = random.nextInt(total);
while (matrix[rand / col][rand % col] == 1) {
rand = random.nextInt(total);
}

matrix[rand / col][rand % col] = 1;
return new int[]{rand / col, rand % col};
}

public void reset() {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
matrix[i][j] = 0;
}
}
}
}

复杂度分析:

  • 时间复杂度:

    • flip\texttt{flip}O(mn)O(mn)
    • reset\texttt{reset}O(mn)O(mn)
  • 空间复杂度:O(mn)O(mn),需要 mnmn 的空间来存储矩阵。

方法二:降维 + 哈希表记录交换

思路与算法:

方法一需要新建一个二维数组,而 mmnn 都是 10410^4,乘起来是 10810^8,维护如此之大的数组是非常耗费内存和时间的。有没有什么方法可以优化呢?

注意到最多调用 10001000flip()\texttt{flip()}reset()\texttt{reset()} 方法,那么有没有办法可以只记录已经用过的数,还记得 384. 打乱数组 中洗牌算法中是如何交换数的吗?

将矩阵转换为一个长度为 m×nm \times n 的一维数组 map\textit{map},对于矩阵中的位置 (i,j)(i, j),它对应了 map\textit{map}中的元素 map[i×n+j]\textit{map}[i \times n + j],这样就保证了矩阵和 mapmap 的元素映射。在经过 m×nkm \times n - k 次翻转 flip\texttt{flip} 后,我们会修改 map\textit{map} 与矩阵的映射,使得当前矩阵中有 m×nkm \times n - k11kk00

使用一个 HashMap\texttt{HashMap} 存储那些 map\textit{map} 中那些被修改了的映射。

对于一个数 xx

  1. 如果 xx 不是 HashMap\texttt{HashMap} 中的一个键,那么它直接映射到最开始的 (x/n,xmodn)(x/n, x \mod n)

  2. 如果 xxHashMap\texttt{HashMap} 中的一个键,那么它映射到其在 HashMap\texttt{HashMap} 中对应的值。

实际运行中 HashMap\texttt{HashMap} 的大小仅和翻转次数成正比,因为每一次翻转操作我们会交换 map\textit{map} 中两个元素的映射,即最多有两个元素的映射关系被修改。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
static class Solution {
int row;
int col;
int total;
Map<Integer, Integer> map;
Random random = new Random();

public Solution(int m, int n) {
row = m;
col = n;
map = new HashMap<>();
total = row * col;
}

public int[] flip() {
int x = random.nextInt(total);
total--;
int idx = map.getOrDefault(x, x);
map.put(x, map.getOrDefault(total, total));
return new int[]{idx / col, idx % col};
}

public void reset() {
map.clear();
total = row * col;
}
}

复杂度分析:

  • 时间复杂度:

    • flip\texttt{flip}O(1)O(1)
    • reset\texttt{reset}O(F)O(F),其中 FF 是在上一次 reset()\texttt{reset}() 之后执行 flip()\texttt{flip}() 的次数。
  • 空间复杂度:O(F)O(F),其中 FF 代表执行函数 flip()\texttt{flip}() 的次数。


All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗