[LeetCode][519. 随机翻转矩阵] 2种方法:暴力法 和 降维 + 哈希表
By Long Luo
Leetcode 519. 随机翻转矩阵 题目如下:
1 | 519. 随机翻转矩阵 |
这道题和 384. 打乱数组 类似,考察的都是随机数的有用,下面我们用暴力法和哈希表 种方法来解决这个问题。
方法一:暴力 + 随机数
思路与算法:
首先就想到的是新建一个矩阵 ,调用 时重置 。
但是调用 呢?
- 生成一个 到 的随机数 ;
- 如果当前数组元素值为 ,说明已经被调用过,需要重新生成一个随机数,返回上一步;
- 如果当前数组元素值为 ,对其置 ,返回当前位置。
代码如下所示:
1 | class Solution { |
复杂度分析:
-
时间复杂度:
- :。
- :。
-
空间复杂度:,需要 的空间来存储矩阵。
方法二:降维 + 哈希表记录交换
思路与算法:
方法一需要新建一个二维数组,而 和 都是 ,乘起来是 ,维护如此之大的数组是非常耗费内存和时间的。有没有什么方法可以优化呢?
注意到最多调用 次 和 方法,那么有没有办法可以只记录已经用过的数,还记得 384. 打乱数组 中洗牌算法中是如何交换数的吗?
将矩阵转换为一个长度为 的一维数组 ,对于矩阵中的位置 ,它对应了 中的元素 ,这样就保证了矩阵和 的元素映射。在经过 次翻转 后,我们会修改 与矩阵的映射,使得当前矩阵中有 个 和 个 。
使用一个 存储那些 中那些被修改了的映射。
对于一个数 :
-
如果 不是 中的一个键,那么它直接映射到最开始的 ;
-
如果 是 中的一个键,那么它映射到其在 中对应的值。
实际运行中 的大小仅和翻转次数成正比,因为每一次翻转操作我们会交换 中两个元素的映射,即最多有两个元素的映射关系被修改。
代码如下所示:
1 | static class Solution { |
复杂度分析:
-
时间复杂度:
- :。
- :,其中 是在上一次 之后执行 的次数。
-
空间复杂度:,其中 代表执行函数 的次数。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗