| comments | difficulty | edit_url | tags | ||||||
|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
|
给定一个 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 <= 1000 <= x, y, z < n- 最多总共调用
105次setCell和unsetCell。 - 最多调用
104次largestMatrix。
我们使用一个三维数组
调用 setCell 方法时，我们先判断
调用 unsetCell 方法时，我们先判断
调用 largestMatrix 方法时，我们返回
时间复杂度方面，setCell 和 unsetCell 方法的时间复杂度均为 largestMatrix 方法的时间复杂度为
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();
*/