LeetCode算法题(Go语言实现)_23

题目

给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。
如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。

一、代码实现

func equalPairs(grid [][]int) int {n := len(grid)rowMap := make(map[string]int)// 统计每行的字符串出现次数for _, row := range grid {var sb strings.Builderfor j, num := range row {if j > 0 {sb.WriteString(",")}sb.WriteString(strconv.Itoa(num))}rowMap[sb.String()]++}count := 0// 遍历每列并匹配行哈希for j := 0; j < n; j++ {var sb strings.Builderfor i := 0; i < n; i++ {if i > 0 {sb.WriteString(",")}sb.WriteString(strconv.Itoa(grid[i][j]))}count += rowMap[sb.String()]}return count
}

二、算法分析

1. 核心思路

   • 哈希映射：通过将行转换为字符串作为哈希键，统计每行的出现次数
   • 对称查询：遍历列并生成相同格式的字符串，查询哈希表实现快速匹配

2. 关键步骤

   • 行统计阶段：将每行元素拼接为逗号分隔字符串（如"3,1,2,2"）存入哈希表
   • 列匹配阶段：对每列生成相同格式字符串，累加哈希表中对应键的值
   • 去重机制：利用字符串天然的唯一性保证行列元素的严格匹配

3. 复杂度

   指标	值	说明
   时间复杂度	O(n²)	遍历行列各需O(n²)时间
   空间复杂度	O(n²)	哈希表存储所有行的字符串

三、图解示例

四、边界条件与扩展

1. 特殊场景处理

   • 全相同矩阵：如[[1,1],[1,1]]，返回4（每个行列都匹配）
   • 空矩阵：根据题意n≥1，无需处理
   • 巨型元素：字符串拼接兼容大整数，无需特殊处理

2. 多语言实现

# Python利用元组哈希特性
def equalPairs(grid):row_counts = defaultdict(int)for row in grid:row_counts[tuple(row)] += 1count = 0n = len(grid)for j in range(n):column = tuple(grid[i][j] for i in range(n))count += row_counts.get(column, 0)return count

// Java使用行列对象哈希
public int equalPairs(int[][] grid) {Map<List<Integer>, Integer> map = new HashMap<>();int n = grid.length;for (int[] row : grid) {List<Integer> key = new ArrayList<>();for (int num : row) key.add(num);map.put(key, map.getOrDefault(key, 0) + 1);}int res = 0;for (int j = 0; j < n; j++) {List<Integer> col = new ArrayList<>();for (int i = 0; i < n; i++) col.add(grid[i][j]);res += map.getOrDefault(col, 0);}return res;
}

3. 算法对比

方法	时间复杂度	空间复杂度	优势
哈希映射法	O(n²)	O(n²)	最优时间复杂度
暴力枚举法	O(n³)	O(1)	实现简单
矩阵压缩法	O(n²)	O(n)	空间优化但实现复杂

五、总结与扩展

• 数学本质：利用集合论中的笛卡尔积特性，将行列匹配转化为集合交运算
• 工程优化：采用字符串哈希替代数组比较，减少内存占用（相比存储整型数组）
• 扩展应用：
  1. 基因序列比对：检测DNA碱基链的互补匹配
  2. 图像模式识别：匹配行列像素分布模式
  3. 推荐系统：通过用户-商品矩阵寻找行为相似行列