519.随机翻转矩阵

链接：519.随机翻转矩阵
难度：Medium
标签：水塘抽样、哈希表、数学、随机化
简介：给你一个 m x n 的二元矩阵 matrix ，且所有值被初始化为 0 。请你设计一个算法，随机选取一个满足  matrix[i][j] == 0 的下标  (i, j) ，并将它的值变为 1 。所有满足 matrix[i][j] == 0 的下标 (i, j) 被选取的概率应当均等。

题解 1 - typescript

• 编辑时间：2021-11-27
• 执行用时：100ms
• 内存消耗：43.8MB
• 编程语言：typescript
• 解法介绍：随机值，每次遍历到一个位置，把该位置与最后一个位置进行交换。

class Solution {
  map = new Map<number, number>();
  total: number;
  constructor(public m: number, public n: number) {
    this.total = m * n;
  }
  flip(): number[] {
    const num = this.random(0, --this.total);
    const idx = this.map.get(num) ?? num;
    this.map.set(num, this.map.get(this.total) ?? this.total);
    return [Math.floor(idx / this.n), idx % this.n];
  }
  reset(): void {
    this.map.clear();
    this.total = this.m * this.n;
  }
  random(min: number, max: number): number {
    return min + Math.floor(Math.random() * (max - min + 1));
  }
}