相等行列对【LC2352】
给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目*。*
如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。
映射+哈希表
- 思路
将每个数字映射为字符，那么可以将每行每列用字符串表示，然后求出每行对应的字符串及其出现次数，再求出每列对应的字符串，如果存在相同的行，那么累加行出现的次数 - 实现
class Solution { public int equalPairs(int[][] grid) { int n = grid.length; int res = 0; HashMap<String, Integer> map = new HashMap<>(); for (int i = 0; i < n; i++){ StringBuilder row = new StringBuilder(); for (int j = 0; j < n; j++){ row.append((char)('0' + grid[i][j])); } map.put(row.toString(), map.getOrDefault(row.toString(), 0) + 1); } for (int i = 0; i < n; i++){ StringBuilder col = new StringBuilder(); for (int j = 0; j < n; j++){ col.append((char)('0' + grid[j][i])); } res += map.getOrDefault(col.toString(), 0); } return res; } }
复杂度
- 时间复杂度：O(n3)，双重循环O(n2)+字符串放入哈希表O(n)
- 空间复杂度：O(n2)
字符串哈希
- 思路不熟悉字符串哈希的看这里将每行每列使用字符串哈希算法进行编码，其他同上
grid[i][j]相当于某个字符的整数形式，所以1-11和11-1所代表的值是不同的
- 实现
class Solution { public int equalPairs(int[][] grid) { int n = grid.length; int base = 7; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < n; i++){ int h = 0; for (int j = 0; j < n; j++){ h = h * base + grid[i][j]; } map.put(h, map.getOrDefault(h, 0) + 1); } int res = 0; for (int i = 0; i < n; i++){ int h = 0; for (int j = 0; j < n; j++){ h = h * base + grid[j][i]; } res += map.getOrDefault(h, 0); } return res; } }
复杂度
- 时间复杂度：O(n2)，双重循环O(n2)+数字放入哈希表O(1)
- 空间复杂度：O(n)
