题目描述
给你一个下标从 0 开始、大小为 m x n
的二维矩阵 grid
,请你求解大小同样为 m x n
的答案矩阵 answer
。
矩阵 answer
中每个单元格 (r, c)
的值可以按下述方式进行计算:
- 令
topLeft[r][c]
为矩阵grid
中单元格(r, c)
左上角对角线上 不同值 的数量。 - 令
bottomRight[r][c]
为矩阵grid
中单元格(r, c)
右下角对角线上 不同值 的数量。
然后 answer[r][c] = |topLeft[r][c] - bottomRight[r][c]|
。
返回矩阵 answer
。
矩阵对角线 是从最顶行或最左列的某个单元格开始,向右下方向走到矩阵末尾的对角线。
如果单元格 (r1, c1)
和单元格 (r, c)
属于同一条对角线且 r1 < r
,则单元格 (r1, c1)
属于单元格 (r, c)
的左上对角线。类似地,可以定义右下对角线。
样例
输入:grid = [[1,2,3],[3,1,5],[3,2,1]]
输出:[[1,1,0],[1,0,1],[0,1,1]]
解释:第 1 个图表示最初的矩阵 grid 。
第 2 个图表示对单元格 (0,0) 计算,其中蓝色单元格是位于右下对角线的单元格。
第 3 个图表示对单元格 (1,2) 计算,其中红色单元格是位于左上对角线的单元格。
第 4 个图表示对单元格 (1,1) 计算,其中蓝色单元格是位于右下对角线的单元格,
红色单元格是位于左上对角线的单元格。
- 单元格 (0,0) 的右下对角线包含 [1,1],而左上对角线包含 []。对应答案是 |1 - 0| = 1。
- 单元格 (1,2) 的右下对角线包含 [],而左上对角线包含 [2]。对应答案是 |0 - 1| = 1。
- 单元格 (1,1) 的右下对角线包含 [1],而左上对角线包含 [1]。对应答案是 |1 - 1| = 0。
其他单元格的对应答案也可以按照这样的流程进行计算。
输入:grid = [[1]]
输出:[[0]]
解释:- 单元格 (0,0) 的右下对角线包含 [],左上对角线包含 []。对应答案是 |0 - 0| = 0。
限制
m == grid.length
n == grid[i].length
1 <= m, n, grid[i][j] <= 50
算法
(前后缀分解) $O(mn+ S)$
- 对于每条对角线,都通过前后缀分解的方式,在线性时间内求出所有位置的答案。
- 假设给定一个数组,求出数组每个位置前后缀不同数字的差值,则可以先预处理出现次数数组,统计出每个数字出现的次数,和不同的数字个数。
- 然后从后向前遍历数组,遍历过程中按照同样的方式统计后缀不同数字出现的次数,且不断在权值数组中减去对应数字的出现次数,并修改前缀不同数字的个数。每次遍历更新答案。
时间复杂度
- 假设最大的数字为 $S$,每个位置仅被遍历两次,故总时间复杂度为 $O(mn + S)$。
空间复杂度
- 需要 $O(mn + S)$ 的额外空间存储答案和出现次数数组。
C++ 代码
const int N = 50;
class Solution {
private:
int m, n;
vector<vector<int>> ans;
int sum[N + 10];
bool seen[N + 10];
void solve(int x, int y, const vector<vector<int>>& grid) {
memset(sum, 0, sizeof(sum));
memset(seen, false, sizeof(seen));
int pre = 0, suf = 0;
while (x < m && y < n) {
if (sum[grid[x][y]] == 0)
++pre;
++sum[grid[x][y]];
++x; ++y;
}
--x; --y;
while (x >= 0 && y >= 0) {
if (sum[grid[x][y]] == 1)
--pre;
--sum[grid[x][y]];
ans[x][y] = abs(pre - suf);
if (!seen[grid[x][y]]) {
++suf;
seen[grid[x][y]] = true;
}
--x; --y;
}
}
public:
vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {
m = grid.size(); n = grid[0].size();
ans.resize(m, vector<int>(n));
for (int i = 0; i < m; i++)
solve(i, 0, grid);
for (int j = 1; j < n; j++)
solve(0, j, grid);
return ans;
}
};