在线自助设计平台_濮阳网最新信息_热搜在哪里可以看_手机百度助手

一、题目描述

给你一个 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 方法。

二、解题思路

1. 使用一个哈希表来记录已经被翻转的坐标，这样可以避免在矩阵中直接修改值，减少空间复杂度。
2. 使用一个变量来记录当前总共剩余的可翻转的坐标数量。
3. 在 flip() 方法中，生成一个随机数，代表从剩余的可翻转坐标中随机选择一个。然后，将该坐标从哈希表中移除，并在返回坐标的同时将其标记为已翻转。
4. 在 reset() 方法中，清空哈希表，并重置剩余可翻转坐标的数量。

三、具体代码

import java.util.HashMap;
import java.util.Map;
import java.util.Random;class Solution {private int m;private int n;private int remaining;private Map<Integer, Integer> flipped;private Random random;public Solution(int m, int n) {this.m = m;this.n = n;this.remaining = m * n;this.flipped = new HashMap<>();this.random = new Random();}public int[] flip() {// 生成一个随机数int randIndex = random.nextInt(remaining);// 计算实际的坐标int actualIndex = randIndex;for (int key : flipped.keySet()) {if (randIndex >= key) {actualIndex++;} else {break;}}int i = actualIndex / n;int j = actualIndex % n;// 记录该坐标已经被翻转flipped.put(actualIndex, actualIndex);// 减少剩余可翻转的数量remaining--;return new int[]{i, j};}public void reset() {flipped.clear();remaining = m * n;}
}/*** Your Solution object will be instantiated and called as such:* Solution obj = new Solution(m, n);* int[] param_1 = obj.flip();* obj.reset();*/

这个实现中，我们通过哈希表 flipped 来记录已经被翻转的坐标的索引（而不是坐标本身），这样可以避免在矩阵中直接修改值，从而节省空间。每次调用 flip() 时，我们通过随机数生成器选择一个未被翻转的坐标，并将其记录下来。调用 reset() 时，我们清空哈希表并重置剩余可翻转坐标的数量。这样，我们保证了每次调用 flip() 时，每个未被翻转的坐标被选中的概率是相等的。

四、时间复杂度和空间复杂度

1. 时间复杂度

• Solution(int m, int n) 构造函数的时间复杂度是 O(1)，因为它只执行了几个赋值操作。
• flip() 方法的时间复杂度在最坏情况下是 O(m * n)。这是因为我们需要遍历 flipped 哈希表来找到实际的下标。在最坏的情况下，即当所有的坐标都已经被翻转过，哈希表的大小将接近 m * n，因此我们需要遍历整个哈希表来找到未被翻转的坐标。每次调用 flip() 时，最坏情况下需要遍历整个哈希表。
• reset() 方法的时间复杂度是 O(m * n)，因为我们需要清空哈希表，这将遍历所有的元素并释放它们。

2. 空间复杂度

• Solution(int m, int n) 构造函数的空间复杂度是 O(1)，因为它只存储了几个整型变量和一个哈希表，但哈希表此时为空。
• flip() 方法本身不占用额外的空间，但是随着方法的多次调用，flipped 哈希表会逐渐增长。在最坏的情况下，即当所有的坐标都被翻转过，哈希表将包含 m * n 个条目。因此，空间复杂度是 O(m * n)。
• reset() 方法不占用额外的空间，它只是重置了哈希表和 remaining 变量。

综上所述，对于整个 Solution 类：

• 时间复杂度：构造函数 O(1)，flip() 方法 O(m * n)，reset() 方法 O(m * n)。
• 空间复杂度：O(m * n)，这是由于 flipped 哈希表在最坏情况下可能包含 m * n 个条目。

请注意，虽然 flip() 方法在最坏情况下的时间复杂度是 O(m * n)，但是在实际应用中，由于每次调用 flip() 都会减少一个可翻转的坐标，因此平均情况下，flip() 方法的时间复杂度会低于 O(m * n)。实际上，平均时间复杂度更接近于 O(1)，因为大多数情况下，我们不需要遍历整个哈希表。然而，在最坏情况下，即当所有的坐标都被翻转过，我们确实需要遍历整个哈希表，因此最坏情况下的时间复杂度仍然是 O(m * n)。

五、总结知识点

• 类定义：

  • class 关键字用于定义一个类。
  • 类可以有成员变量和方法。

• 成员变量：

  • 成员变量（字段）是在类的所有方法之外声明的变量，它们可以在类的任何方法中使用。
  • private 关键字用于声明私有成员变量，它们只能在类的内部访问。

• 构造函数：

  • 构造函数是一种特殊的方法，用于创建类的实例时初始化对象。
  • 构造函数的名称必须与类名相同。

• 方法：

  • 方法是类中定义的函数，用于执行特定操作。
  • public 关键字用于声明公共方法，它们可以被类的实例外部访问。

• 数据结构：

  • HashMap 是一种基于哈希表的映射数据结构，用于存储键值对。
  • Map 是一个接口，提供了操作键值对的方法。

• 随机数生成：

  • Random 类用于生成伪随机数。
  • nextInt(int bound) 方法用于生成一个介于 0（包含）和指定值（不包含）之间的随机整数。

• 算术运算：

  • 使用基本的算术运算符（+, -, *, /, %）进行数学计算。

• 逻辑控制：

  • 使用 for 循环遍历集合。
  • 使用 if-else 语句进行条件判断。

• 方法重置：

  • reset() 方法用于将对象的状态重置为初始状态。

• 方法返回值：

  • 方法可以返回一个值，使用 return 关键字。

• 数组：

  • 使用数组来存储多个值，例如返回坐标。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。