相等行列对
难度:
标签:
题目描述
给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。
如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。
示例 1：
输入：grid = [[3,2,1],[1,7,6],[2,7,7]] 输出：1 解释：存在一对相等行列对： - (第 2 行，第 1 列)：[2,7,7]
示例 2：
输入：grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]] 输出：3 解释：存在三对相等行列对： - (第 0 行，第 0 列)：[3,1,2,2] - (第 2 行, 第 2 列)：[2,4,2,2] - (第 3 行, 第 2 列)：[2,4,2,2]
提示：
n == grid.length == grid[i].length1 <= n <= 2001 <= grid[i][j] <= 105
代码结果
运行时间: 51 ms, 内存: 20.4 MB
/*
* Solution for LeetCode problem using Java Streams:
* Given a 2D integer matrix grid of size n x n, return the number of pairs (Ri, Cj) where the i-th row and j-th column are equal.
* Two arrays are considered equal if they contain the same elements in the same order.
*/
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
public class EqualRowColumnPairsStream {
public int equalPairs(int[][] grid) {
int n = grid.length;
Map<String, Long> rowCount = new HashMap<>();
for (int[] row : grid) {
String key = Arrays.toString(row);
rowCount.put(key, rowCount.getOrDefault(key, 0L) + 1);
}
return (int) IntStream.range(0, n).flatMap(j -> {
int[] col = new int[n];
for (int i = 0; i < n; i++) {
col[i] = grid[i][j];
}
String key = Arrays.toString(col);
return rowCount.getOrDefault(key, 0L).intValue();
}).sum();
}
public static void main(String[] args) {
EqualRowColumnPairsStream solution = new EqualRowColumnPairsStream();
int[][] grid1 = { {3, 2, 1}, {1, 7, 6}, {2, 7, 7} };
int[][] grid2 = { {3, 1, 2, 2}, {1, 4, 4, 5}, {2, 4, 2, 2}, {2, 4, 2, 2} };
System.out.println(solution.equalPairs(grid1)); // Output: 1
System.out.println(solution.equalPairs(grid2)); // Output: 3
}
}解释
方法:
该题解首先将矩阵的每一行转换为元组并存储在列表a中。使用collections.Counter计算列表a中每种元组出现的次数，存储在a1中。然后，它遍历矩阵的每一列（通过对grid使用zip(*)来获得列），并检查每个列元组在a1中的出现次数。如果该列元组存在于a1中，则将其计数加到总数c中。最终，返回总数c，即相等的行列对的数量。
时间复杂度:
O(n^2)
空间复杂度:
O(n^2)
代码细节讲解
🦆
为什么在计算行元组时选择使用元组而不是列表？
▷🦆
题解提到变量`b`未被使用，这是否意味着代码存在冗余，如何改进代码以提高其效率和可读性？
▷