3391. 设计一个高效的层跟踪三维二进制矩阵 🔒

题目描述

给定一个 n x n x n 的 二进制 三维数组 matrix。

实现 Matrix3D 类：

• Matrix3D(int n) 用三维二进制数组 matrix 初始化对象，其中 所有 元素都初始化为 0。
• void setCell(int x, int y, int z) 将 matrix[x][y][z] 的值设为 1。
• void unsetCell(int x, int y, int z) 将 matrix[x][y][z] 的值设为 0。
• int largestMatrix() 返回包含最多 1 的 matrix[x] 的下标 x。如果这样的对应值有多个，返回 最大的 x。

 

示例 1：

输入：
["Matrix3D", "setCell", "largestMatrix", "setCell", "largestMatrix", "setCell", "largestMatrix"]
[[3], [0, 0, 0], [], [1, 1, 2], [], [0, 0, 1], []]

输出：
[null, null, 0, null, 1, null, 0]

解释：

Matrix3D matrix3D = new Matrix3D(3); // 初始化一个 3 x 3 x 3 的三维数组 matrix，用全 0 填充。
matrix3D.setCell(0, 0, 0); // 将 matrix[0][0][0] 设为 1。
matrix3D.largestMatrix(); // 返回 0。matrix[0] 1 的数量最多。
matrix3D.setCell(1, 1, 2); // 将 matrix[1][1][2] 设为 1。
matrix3D.largestMatrix(); // 返回 1。matrix[0] 和 matrix[1] 1 的数量一样多，但下标 1 更大。
matrix3D.setCell(0, 0, 1); // 将 matrix[0][0][1] 设为 1。
matrix3D.largestMatrix(); // 返回 0。matrix[0] 1 的数量最多。

示例 2：

输入：
["Matrix3D", "setCell", "largestMatrix", "unsetCell", "largestMatrix"]
[[4], [2, 1, 1], [], [2, 1, 1], []]

输出：
[null, null, 2, null, 3]

解释：

Matrix3D matrix3D = new matrix3D(4); // 初始化一个 4 x 4 x 4 的三维数组 matrix，用全 0 填充。
matrix3D.setCell(2, 1, 1); // 将 matrix[2][1][1] 设为 1。
matrix3D.largestMatrix(); // 返回 2。matrix[2] 1 的数量最多。
matrix3D.unsetCell(2, 1, 1); // 将 matrix[2][1][1] 设为 0。
matrix3D.largestMatrix(); // 返回 3。0 到 3 的对应值都有相同数量的 1，但下标 3 最大。

 

提示：

• 1 <= n <= 100
• 0 <= x, y, z < n
• 最多总共调用 105 次 setCell 和 unsetCell。
• 最多调用 104 次 largestMatrix。

解法

方法一：计数 + 有序集合

我们使用一个三维数组 \(\textit{g}\) 来表示矩阵，其中 \(\textit{g}[x][y][z]\) 表示矩阵中坐标 \((x, y, z)\) 的值，用一个长度为 \(n\) 的数组 \(\textit{cnt}\) 来记录每一层的 \(1\) 的个数，用一个有序集合 \(\textit{sl}\) 来维护每一层的 \(1\) 的个数和层数，其中 \(\textit{sl}\) 中的元素是 \((\textit{cnt}[x], x)\)，这样 \(\textit{sl}\) 就能按照 \(1\) 的个数降序排序，如果 \(1\) 的个数相同，则按照层数降序排序。

调用 setCell 方法时，我们先判断 \((x, y, z)\) 是否已经被设置为 \(1\)，如果是则直接返回，否则将 \(\textit{g}[x][y][z]\) 设置为 \(1\)，然后将 \((\textit{cnt}[x], x)\) 从 \(\textit{sl}\) 中删除，将 \(\textit{cnt}[x]\) 加一，再将 \((\textit{cnt}[x], x)\) 加入 \(\textit{sl}\)。

调用 unsetCell 方法时，我们先判断 \((x, y, z)\) 是否已经被设置为 \(0\)，如果是则直接返回，否则将 \(\textit{g}[x][y][z]\) 设置为 \(0\)，然后将 \((\textit{cnt}[x], x)\) 从 \(\textit{sl}\) 中删除，将 \(\textit{cnt}[x]\) 减一，如果 \(\textit{cnt}[x]\) 大于 \(0\)，则将 \((\textit{cnt}[x], x)\) 加入 \(\textit{sl}\)。

调用 largestMatrix 方法时，我们返回 \(\textit{sl}\) 中第一个元素的第二个值，如果 \(\textit{sl}\) 为空，则返回 \(n - 1\)。

时间复杂度方面，setCell 和 unsetCell 方法的时间复杂度均为 \(O(\log n)\)，largestMatrix 方法的时间复杂度为 \(O(1)\)。空间复杂度 \(O(n^3)\)。

Python3JavaC++Go

class matrix3D:

    def __init__(self, n: int):
        self.g = [[[0] * n for _ in range(n)] for _ in range(n)]
        self.cnt = [0] * n
        self.sl = SortedList(key=lambda x: (-x[0], -x[1]))

    def setCell(self, x: int, y: int, z: int) -> None:
        if self.g[x][y][z]:
            return
        self.g[x][y][z] = 1
        self.sl.discard((self.cnt[x], x))
        self.cnt[x] += 1
        self.sl.add((self.cnt[x], x))

    def unsetCell(self, x: int, y: int, z: int) -> None:
        if self.g[x][y][z] == 0:
            return
        self.g[x][y][z] = 0
        self.sl.discard((self.cnt[x], x))
        self.cnt[x] -= 1
        if self.cnt[x]:
            self.sl.add((self.cnt[x], x))

    def largestMatrix(self) -> int:
        return self.sl[0][1] if self.sl else len(self.g) - 1


# Your matrix3D object will be instantiated and called as such:
# obj = matrix3D(n)
# obj.setCell(x,y,z)
# obj.unsetCell(x,y,z)
# param_3 = obj.largestMatrix()

class matrix3D {
    private final int[][][] g;
    private final int[] cnt;
    private final TreeSet<int[]> sl
        = new TreeSet<>((a, b) -> a[0] == b[0] ? b[1] - a[1] : b[0] - a[0]);

    public matrix3D(int n) {
        g = new int[n][n][n];
        cnt = new int[n];
    }

    public void setCell(int x, int y, int z) {
        if (g[x][y][z] == 1) {
            return;
        }
        g[x][y][z] = 1;
        sl.remove(new int[] {cnt[x], x});
        cnt[x]++;
        sl.add(new int[] {cnt[x], x});
    }

    public void unsetCell(int x, int y, int z) {
        if (g[x][y][z] == 0) {
            return;
        }
        g[x][y][z] = 0;
        sl.remove(new int[] {cnt[x], x});
        cnt[x]--;
        if (cnt[x] > 0) {
            sl.add(new int[] {cnt[x], x});
        }
    }

    public int largestMatrix() {
        return sl.isEmpty() ? g.length - 1 : sl.first()[1];
    }
}

/**
 * Your matrix3D object will be instantiated and called as such:
 * matrix3D obj = new matrix3D(n);
 * obj.setCell(x,y,z);
 * obj.unsetCell(x,y,z);
 * int param_3 = obj.largestMatrix();
 */

class matrix3D {
private:
    vector<vector<vector<int>>> g;
    vector<int> cnt;
    set<pair<int, int>> sl;

public:
    matrix3D(int n) {
        g.resize(n, vector<vector<int>>(n, vector<int>(n, 0)));
        cnt.resize(n, 0);
    }

    void setCell(int x, int y, int z) {
        if (g[x][y][z] == 1) {
            return;
        }
        g[x][y][z] = 1;
        sl.erase({-cnt[x], -x});
        cnt[x]++;
        sl.insert({-cnt[x], -x});
    }

    void unsetCell(int x, int y, int z) {
        if (g[x][y][z] == 0) {
            return;
        }
        g[x][y][z] = 0;
        sl.erase({-cnt[x], -x});
        cnt[x]--;
        if (cnt[x]) {
            sl.insert({-cnt[x], -x});
        }
    }

    int largestMatrix() {
        return sl.empty() ? g.size() - 1 : -sl.begin()->second;
    }
};

/**
 * Your matrix3D object will be instantiated and called as such:
 * matrix3D* obj = new matrix3D(n);
 * obj->setCell(x,y,z);
 * obj->unsetCell(x,y,z);
 * int param_3 = obj->largestMatrix();
 */

评论