Medium

题目描述

有一个 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

示例 1：

输入
["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

解题思路

这道题目的关键是在不实际创建矩阵的情况下，实现随机选择未翻转位置的功能。

核心思路：水库采样 + 映射交换

我们将矩阵的每个位置映射到一个一维数组的索引：位置 (i,j) 对应索引 i*n+j。这样 m×n 的矩阵就对应了 0 到 total-1 的索引范围。

关键思想是维护一个"虚拟数组"，其中：

  • 前 total 个位置表示还未被翻转的位置
  • 当我们翻转一个位置时，将其与数组末尾交换，然后缩小有效范围

具体实现：

  1. 用哈希表记录被"交换"的映射关系
  2. 每次 flip() 时，在 [0, total-1] 范围内随机选择一个索引
  3. 如果该索引在哈希表中，说明它实际对应别的值；否则就是它本身
  4. 将选中的位置与末尾位置交换（通过哈希表记录），然后 total--
  5. reset() 时清空哈希表，重置 total

这种方法的优势：

  • 空间复杂度：O(翻转次数)，而不是O(m×n)
  • 时间复杂度：每次操作O(1)
  • 保证等概率选择

推荐解法： 基于哈希表的映射交换法

代码实现

class Solution {
private:
    int m, n, total;
    unordered_map<int, int> map;
    
public:
    Solution(int m, int n) : m(m), n(n), total(m * n) {
        srand(time(nullptr));
    }
    
    vector<int> flip() {
        int rand_idx = rand() % total;
        int actual_idx = map.count(rand_idx) ? map[rand_idx] : rand_idx;
        
        map[rand_idx] = map.count(total - 1) ? map[total - 1] : total - 1;
        total--;
        
        return {actual_idx / n, actual_idx % n};
    }
    
    void reset() {
        map.clear();
        total = m * n;
    }
};

class Solution:
    def __init__(self, m: int, n: int):
        self.m = m
        self.n = n
        self.total = m * n
        self.map = {}
    
    def flip(self) -> List[int]:
        import random
        rand_idx = random.randint(0, self.total - 1)
        actual_idx = self.map.get(rand_idx, rand_idx)
        
        self.map[rand_idx] = self.map.get(self.total - 1, self.total - 1)
        self.total -= 1
        
        return [actual_idx // self.n, actual_idx % self.n]
    
    def reset(self) -> None:
        self.map.clear()
        self.total = self.m * self.n

public class Solution {
    private int m, n, total;
    private Dictionary<int, int> map;
    private Random random;

    public Solution(int m, int n) {
        this.m = m;
        this.n = n;
        this.total = m * n;
        this.map = new Dictionary<int, int>();
        this.random = new Random();
    }
    
    public int[] Flip() {
        int randIdx = random.Next(total);
        int actualIdx = map.ContainsKey(randIdx) ? map[randIdx] : randIdx;
        
        map[randIdx] = map.ContainsKey(total - 1) ? map[total - 1] : total - 1;
        total--;
        
        return new int[] { actualIdx / n, actualIdx % n };
    }
    
    public void Reset() {
        map.Clear();
        total = m * n;
    }
}

var Solution = function(m, n) {
    this.m = m;
    this.n = n;
    this.total = m * n;
    this.map = new Map();
};

Solution.prototype.flip = function() {
    const randIdx = Math.floor(Math.random() * this.total);
    const actualIdx = this.map.has(randIdx) ? this.map.get(randIdx) : randIdx;
    
    this.map.set(randIdx, this.map.has(this.total - 1) ? this.map.get(this.total - 1) : this.total - 1);
    this.total--;
    
    return [Math.floor(actualIdx / this.n), actualIdx % this.n];
};

Solution.prototype.reset = function() {
    this.map.clear();
    this.total = this.m * this.n;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
构造函数O(1)O(1)
flip()O(1)O(k)
reset()O(1)O(1)

其中 k 是已经翻转的位置数量，最大为 min(1000, m×n)