leetcode
leetcode 801 ~ 850
随机翻转矩阵

随机翻转矩阵

难度:

标签:

题目描述

代码结果

运行时间: 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)`被选中的概率是均等的?
在flip函数中,每次选择一个随机索引`r`时,都是从当前未被选中的索引范围`[0, self.total]`中随机选取的。由于每次选择后,`self.total`都会减少1,并且通过哈希表的映射机制确保任何已经被选择的索引都映射到一个未被选择的新索引上,这样每个索引在每次调用`flip`时被选中的机会都是均等的,保证了每个索引被选中的概率是相同的。
🦆
在哈希表中,如果一个索引已经被选取并映射到一个新的未被选取的索引,那么这种映射方法是否会导致某些索引被选中的概率变高?
不会。映射方法的设计是为了确保每个索引被选中的概率保持一致。当一个索引`r`被选中后,通过映射将其指向另一个尚未被选中的索引(通常是当前的`self.total`索引)。这种映射确保了即使`r`已经被使用,后续选择时它仍指向一个有效的未使用索引。因此,每个索引被选中的次数在长期运行中将均等分布,不会因映射机制而有所偏差。
🦆
reset函数是否能够完全重置`Solution`类的状态,使其与初始化后的状态完全相同?
是的,reset函数将`self.total`重置为`m * n - 1`,并且清空了哈希表`self.record`。这确保了类的状态完全回到了初始状态,如同新创建一个实例一样,所有的索引都重新变为可选,并且没有任何映射记录。
🦆
在flip操作中,使用`self.record.get(r, r)`和`self.record.get(self.total, self.total)`进行索引映射的具体逻辑是什么?
`self.record.get(r, r)`表示尝试从哈希表`self.record`中获取键`r`的值,如果`r`不存在,则返回`r`自身。这确保了即使某个索引尚未映射,它也能正确返回自身作为结果。`self.record.get(self.total, self.total)`用于更新映射表,表示如果`self.total`已经有映射,则使用其映射值,否则使用`self.total`自身。这种方法在每次flip调用时,都将已选索引`r`映射到当前最末尾的索引`self.total`,保持映射的连续性和有效性,从而确保所有索引能均等地被随机选择。

相关问题