专栏首页眯眯眼猫头鹰的小树杈leetcode519. Random Flip Matrix

leetcode519. Random Flip Matrix

题目要求

You are given the number of rows n_rows and number of columns n_cols of a 2D binary matrix where all values are initially 0. Write a function flip which chooses a 0 value uniformly at random, changes it to 1, and then returns the position [row.id, col.id] of that value. Also, write a function reset which sets all values back to 0. Try to minimize the number of calls to system's Math.random() and optimize the time and space complexity.

Note:

  1. 1 <= n_rows, n_cols <= 10000
  2. 0 <= row.id < n_rows and 0 <= col.id < n_cols
  3. flip will not be called when the matrix has no 0 values left.
  4. the total number of calls to flip and reset will not exceed 1000.

Example 1:

Input: 
["Solution","flip","flip","flip","flip"]
[[2,3],[],[],[],[]]
Output: [null,[0,1],[1,2],[1,0],[1,1]]

Example 2:

Input: 
["Solution","flip","flip","reset","flip"]
[[1,2],[],[],[],[]]
Output: [null,[0,0],[0,1],null,[0,0]]
Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has two arguments, n_rows and n_cols. flip and reset have no arguments. Arguments are always wrapped with a list, even if there aren't any.

假设现在有一个n_rows行和n_columns列的矩阵,该矩阵中初始时每一个元素值均为0。调用flip方法时需要随机选择矩阵中一个值为0的格子并设置为1,返回格子的行列坐标。reset方法会将矩阵重制为初始状态。要求尽可能减少random方法的调用次数。

思路和代码

其实最直观的方法就是使用随机数分别生成随机的行和列,然后判断该位置上的值是否为0。如果不为0,则继续生成随机行列,继续判断,直到找到为0的格子。

这里的第一个优化就在于将二维数组进行一维化的表示,即第i行第k列这个坐标完全可以通过i*n_columns+k得出唯一的一个整数表示形式。我们只需要对n_rows*n_colums范围内生成一个随机的整数并转化为二维坐标,可以直接将随机方法的执行次数减少一半。

那么接着的优化思路其实可以很直观的想到,如果我们可以保存一个还没有遍历到的下标集合。每次以集合大小作为随机数生成的边界,再从集合中移除该随机数,代表这一次翻了这个位置的格子。

但是直接用List来存储这样的一个结构还是会有很严重的性能问题。假设是一个1000*1000的矩阵,则初始的List中需要存储1000000个未被选中的格子,对于时间和空间来说都是不可接受的。那么有没有办法可以用另一种形式来记录未翻牌的元素下标?

前面已经讲了,二维数组的下标是可以被转化为一维数组下标表示。我们可以想象这样的一个场景,对于这个一维数组,每当一个下标被翻开,都将该下标和位于当前未被翻开的最后一个元素位置进行交换。我们只需要记录叫唤到前面的最后一个元素的新的位置即可。举个例子,2*3的矩阵,可以翻开为一个长度为6的一维矩阵,其元素分别为0,1,2,3,4,5

第一次flip随机生成下标2,则我们将2和5进行交换,并记录2这个位置上新的元素5(2:5) 第二次flip随机生成下标1,则将1和4进行叫唤,并记录1这个位置上新的元素为4(2:5, 1:4) 第三次flip随机生成下标2,此时我们发现2上存的元素是5,因此返回5,经记录2上的新元素为3(2:3, 1:4) 。。。

这样的话,当随机生成的下标不在记录中时,下标上存储的位置就是本身,否则就是交换过的位置。每次都要更新下标上的元素为最后一个还未被翻开的下标。

    Map<Integer, Integer> map;
    Random                r;
    int rowCount;
    int columnCount;
    int flipCount;
    public Solution(int n_rows, int n_cols) {
        map = new HashMap<>();
        r = new Random();
        rowCount = n_rows;
        columnCount = n_cols;
        flipCount = rowCount * columnCount;
    }

    public int[] flip() {
        int randomIndex = r.nextInt(flipCount--);
        int value = map.getOrDefault(randomIndex, randomIndex);
        map.put(randomIndex, map.getOrDefault(flipCount, flipCount));
        return new int[]{value/columnCount, value%columnCount};
    }

    public void reset() {
        map.clear();
        flipCount = rowCount * columnCount;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode375. Guess Number Higher or Lower II

    一个猜数字游戏,数字区间为1~n,每猜一次,会有人告诉你猜中了或者当前的数字是大于结果值还是小于结果值。猜对则本次猜测免费,猜错则本次猜测需要花费和数字等额的金...

    眯眯眼的猫头鹰
  • leetcode495. Teemo Attacking

    In LOL world, there is a hero called Teemo and his attacking can make his enemy ...

    眯眯眼的猫头鹰
  • leetcode452. Minimum Number of Arrows to Burst Balloons

    There are a number of spherical balloons spread in two-dimensional space. For ea...

    眯眯眼的猫头鹰
  • π框架之实战项目(代码分享)

    通过之前的学习,本文主要介绍一下实现用户的登录、注册等功能的接口代码,让大家通过小实战来感悟phalapi框架的神奇之处。(以下代码均可右滑) ? 获取参数规则...

    benny
  • OCP-052考试题库汇总(9)-CUUG内部解答版

    Which three are true about Optimizer Statistics?

    用户5892232
  • HDU 1728 逃离迷宫(DFS经典题,比赛手残写废题)

    逃离迷宫 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

    Angel_Kitty
  • 771. Jewels and Stones

    思路: 记录J的信息,遍历S,采用Hashmap的思路,每次查询O(1),总时间复杂度为O(n)

    用户1147447
  • [浅谈]良师益友“wolf”

    Youngxj
  • idea 项目名称红色 解决办法

    idea如果当前project用了版本控制器,其下面新建的所有的项目默认都是加入到版本控制里面,所以项目名称和文件都是红色的;

    Java架构师历程
  • 线上出bug了?别怕,这么定位!

    工作中,生产环境代码是编译后代码,搜集到报错信息的行和列无法在源码中对应,很多时候只能靠“经验”去猜,本文针对这种情况,开发了一个npm命令行小工具,帮助快速定...

    Fundebug

扫码关注云+社区

领取腾讯云代金券