519.随机翻转矩阵.md

519.随机翻转矩阵

/*
 * @lc app=leetcode.cn id=519 lang=typescript
 *
 * [519] 随机翻转矩阵
 */

// @lc code=start
class Solution {
  constructor(m: number, n: number) {}

  flip(): number[] {}

  reset(): void {}
}

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(m, n)
 * var param_1 = obj.flip()
 * obj.reset()
 */
// @lc code=end

解法 1: 洗牌算法 + 映射

使用哈希表来保存还没被翻转的映射,最多调用 1000 次 flip,这样空间复杂度会小很多.

class Solution {
  _m: number
  _n: number
  _cur: number = 0
  _length: number
  _cache: { [key: number]: number } = {}
  constructor(m: number, n: number) {
    this._m = m
    this._n = n
    this._length = m * n

    this.reset()
  }
  _random(start: number, end: number) {
    return Math.floor(Math.random() * (end - start)) + start
  }

  flip(): number[] {
    const { _random, _cur, _length, _n, _cache } = this
    const index = _random(_cur, _length)
    const select = _cache[index] ?? index
    const i = Math.floor(select / _n),
      j = select % _n

    _cache[index] = _cache[_cur] ?? _cur
    this._cur++
    return [i, j]
  }

  reset(): void {
    this._cache = {}
    this._cur = 0
  }
}