随机翻转矩阵
难度:
标签:
题目描述
代码结果
运行时间: 34 ms, 内存: 16.6 MB
/*
* This implementation of the Solution class uses Java Streams to help with array manipulation.
* It initializes the object with the given dimensions m and n.
* The flip method returns a random index (i, j) where matrix[i][j] == 0 and sets matrix[i][j] = 1.
* The reset method sets all the values of the matrix to 0.
*/
import java.util.*;
import java.util.stream.*;
class Solution {
private int m, n, total;
private Map<Integer, Integer> map;
private Random rand;
public Solution(int m, int n) {
this.m = m;
this.n = n;
this.total = m * n;
this.map = new HashMap<>();
this.rand = new Random();
}
public int[] flip() {
int r = rand.nextInt(total--);
int x = map.getOrDefault(r, r);
map.put(r, map.getOrDefault(total, total));
return Stream.of(x).map(i -> new int[]{i / n, i % n}).findFirst().get();
}
public void reset() {
map.clear();
total = m * n;
}
}
解释
方法:
这个解决方案使用了一个映射表(哈希表)来记录已被随机选取的索引。每当调用flip函数时,它将从未被选择的索引中随机选取一个。使用一个整数total来跟踪还没有被选择的索引数量。如果一个索引已经被选取,它会被哈希表中映射到一个新的未被选取的索引。这样可以避免使用一个完整的矩阵来存储状态,从而节省空间并优化性能。
时间复杂度:
O(1)
空间复杂度:
O(min(m*n, 1000))
代码细节讲解
🦆
如何确保flip函数返回的每个索引`(i, j)`被选中的概率是均等的?
▷🦆
在哈希表中,如果一个索引已经被选取并映射到一个新的未被选取的索引,那么这种映射方法是否会导致某些索引被选中的概率变高?
▷🦆
reset函数是否能够完全重置`Solution`类的状态,使其与初始化后的状态完全相同?
▷🦆
在flip操作中,使用`self.record.get(r, r)`和`self.record.get(self.total, self.total)`进行索引映射的具体逻辑是什么?
▷