跳转至

LeetCode: 519. 随机翻转矩阵

1、题目描述

题中给出一个 n 行 n 列的二维矩阵(n_rows,n_cols),且所有值被初始化为 0。要求编写一个 flip 函数,均匀随机的将矩阵中的 0 变为 1,并返回该值的位置下标[row_id,col_id];同样编写一个 reset 函数,将所有的值都重新置为 0。尽量最少调用随机函数 Math.random(),并且优化时间和空间复杂度。

注意:

  1. 1 <= n_rows, n_cols <= 10000

  2. 0 <= row.id < n_rows 并且 0 <= col.id < n_cols

  3. 当矩阵中没有值为 0 时,不可以调用 flip 函数

  4. 调用 flip 和 reset 函数的次数加起来不会超过 1000 次

示例 1:

输入: 
["Solution","flip","flip","flip","flip"]
[[2,3],[],[],[],[]]
输出: [null,[0,1],[1,2],[1,0],[1,1]]

示例 2:

输入: 
["Solution","flip","flip","reset","flip"]
[[1,2],[],[],[],[]]
输出: [null,[0,0],[0,1],null,[0,0]]

输入语法解释:

输入包含两个列表:被调用的子程序和他们的参数。Solution 的构造函数有两个参数,分别为 n_rows 和 n_cols。flip 和 reset 没有参数,参数总会以列表形式给出,哪怕该列表为空

2、解题思路

  • 采用数字的形式计算坐标
  • 关键点在于如何确认已经使用过的点
  • 保存映射关系,例如当前选择范围中,将当前的选择值与当前最大的范围做映射
  • 如果下一次取到了这个值,依次寻找,找出一个并没有被用过的

  • 所以,关键点就在于如何保存历史关系,记录哪些点是可以使用的

import random


class Solution:

    def __init__(self, n_rows: int, n_cols: int):
        self.n_rows = n_rows
        self.n_cols = n_cols

        self.count = 0
        self.total = n_cols * n_rows - 1

        self.buff = {}

    def flip(self) -> [int]:
        target = random.randint(0, self.total - self.count)
        chosen = target
        while chosen in self.buff:
            chosen = self.buff[chosen]

        self.buff[target] = self.total - self.count
        self.count += 1

        return [chosen // self.n_cols, chosen % self.n_cols]

    def reset(self) -> None:
        self.buff.clear()
        self.count = 0
打印出上面的buff:
随机数:  2357
{2357: 3999}
随机数:  1217
{2357: 3999, 1217: 3998}
随机数:  3488
{2357: 3999, 1217: 3998, 3488: 3997}
随机数:  627
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996}
随机数:  2463
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995}
随机数:  121
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994}
随机数:  3526
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993}
随机数:  3094
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992}
随机数:  2122
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991}
随机数:  1650
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991, 1650: 3990}
随机数:  3528
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991, 1650: 3990, 3528: 3989}
随机数:  3131
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991, 1650: 3990, 3528: 3989, 3131: 3988}
随机数:  819
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991, 1650: 3990, 3528: 3989, 3131: 3988, 819: 3987}
随机数:  2957
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991, 1650: 3990, 3528: 3989, 3131: 3988, 819: 3987, 2957: 3986}
随机数:  427
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991, 1650: 3990, 3528: 3989, 3131: 3988, 819: 3987, 2957: 3986, 427: 3985}
随机数:  3067
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991, 1650: 3990, 3528: 3989, 3131: 3988, 819: 3987, 2957: 3986, 427: 3985, 3067: 3984}
随机数:  1784
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991, 1650: 3990, 3528: 3989, 3131: 3988, 819: 3987, 2957: 3986, 427: 3985, 3067: 3984, 1784: 3983}
随机数:  2591
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991, 1650: 3990, 3528: 3989, 3131: 3988, 819: 3987, 2957: 3986, 427: 3985, 3067: 3984, 1784: 3983, 2591: 3982}
随机数:  1781
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991, 1650: 3990, 3528: 3989, 3131: 3988, 819: 3987, 2957: 3986, 427: 3985, 3067: 3984, 1784: 3983, 2591: 3982, 1781: 3981}
随机数:  1263
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991, 1650: 3990, 3528: 3989, 3131: 3988, 819: 3987, 2957: 3986, 427: 3985, 3067: 3984, 1784: 3983, 2591: 3982, 1781: 3981, 1263: 3980}
随机数:  2637
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991, 1650: 3990, 3528: 3989, 3131: 3988, 819: 3987, 2957: 3986, 427: 3985, 3067: 3984, 1784: 3983, 2591: 3982, 1781: 3981, 1263: 3980, 2637: 3979}
随机数:  2875
{2357: 3999, 1217: 3998, 3488: 3997, 627: 3996, 2463: 3995, 121: 3994, 3526: 3993, 3094: 3992, 2122: 3991, 1650: 3990, 3528: 3989, 3131: 3988, 819: 3987, 2957: 3986, 427: 3985, 3067: 3984, 1784: 3983, 2591: 3982, 1781: 3981, 1263: 3980, 2637: 3979, 2875: 3978}