【Leetcode算法题】519. 随机翻转矩阵

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方法。

方法一:HashMap + 双指针

思路与算法:

代码如下所示:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ans = new ArrayList<>();

int patLen = p.length();
int srcLen = s.length();
if (patLen > srcLen) {
return ans;
}

Map<Character, Integer> patMap = new HashMap<>();
for (char ch : p.toCharArray()) {
patMap.put(ch, patMap.getOrDefault(ch, 0) + 1);
}

int left = 0;
int right = left + patLen;
Map<Character, Integer> winMap = new HashMap<>();
for (int i = left; i < right; i++) {
char ch = s.charAt(i);
winMap.put(ch, winMap.getOrDefault(ch, 0) + 1);
}

if (patMap.equals(winMap)) {
ans.add(left);
}

while (right < srcLen) {
char chRight = s.charAt(right);
winMap.put(chRight, winMap.getOrDefault(chRight, 0) + 1);
char chLeft = s.charAt(left);
if (winMap.get(chLeft) == 1) {
winMap.remove(chLeft);
} else {
winMap.put(chLeft, winMap.get(chLeft) - 1);
}
left++;
right++;
if (patMap.equals(winMap)) {
ans.add(left);
}
}

return ans;
}

复杂度分析:

  • 时间复杂度:O(m+n)O(m + n),其中mm为数组中的元素数量, nn为数组中的元素数量

  • 空间复杂度:O(n)O(n)。记录初始状态和临时的乱序数组均需要存储nn个元素。