Medium

题目描述

给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。

如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。

示例 1：

输入：grid = [[3,2,1],[1,7,6],[2,7,7]]
输出：1
解释：存在 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
解释：存在 3 对相等行列对：
- (第 0 行，第 0 列)：[3,1,2,2]
- (第 2 行，第 2 列)：[2,4,2,2]
- (第 3 行，第 2 列)：[2,4,2,2]

提示：

  • n == grid.length == grid[i].length
  • 1 <= n <= 200
  • 1 <= grid[i][j] <= 10^5

解题思路

本题有两种主要的解决思路：

方法一：暴力比较（推荐） 最直观的方法是对每一行与每一列进行逐一比较。对于每个行i和列j，逐个比较对应位置的元素是否相同。时间复杂度为O(n³)，但实现简单且在给定约束条件下表现良好。

方法二：哈希优化 可以将每行和每列转换为字符串或元组作为哈希键，统计每种模式出现的次数，然后计算匹配对数。先统计所有行的模式频次，再遍历所有列，累加对应模式的频次。这种方法时间复杂度为O(n²)，空间复杂度为O(n²)。

考虑到题目的约束条件（n ≤ 200），暴力方法的性能已经足够，且代码更加直观易懂，因此推荐使用方法一。哈希方法虽然渐近复杂度更优，但在实际小规模数据中可能因为哈希开销而不一定更快。

两种方法都能正确解决问题，可以根据具体需求选择。

代码实现

class Solution {
public:
    int equalPairs(vector<vector<int>>& grid) {
        int n = grid.size();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                bool isEqual = true;
                for (int k = 0; k < n; k++) {
                    if (grid[i][k] != grid[k][j]) {
                        isEqual = false;
                        break;
                    }
                }
                if (isEqual) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        n = len(grid)
        count = 0
        
        for i in range(n):
            for j in range(n):
                is_equal = True
                for k in range(n):
                    if grid[i][k] != grid[k][j]:
                        is_equal = False
                        break
                if is_equal:
                    count += 1
        
        return count

public class Solution {
    public int EqualPairs(int[][] grid) {
        int n = grid.Length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                bool isEqual = true;
                for (int k = 0; k < n; k++) {
                    if (grid[i][k] != grid[k][j]) {
                        isEqual = false;
                        break;
                    }
                }
                if (isEqual) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

var equalPairs = function(grid) {
    const n = grid.length;
    let count = 0;
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            let isEqual = true;
            for (let k = 0; k < n; k++) {
                if (grid[i][k] !== grid[k][j]) {
                    isEqual = false;
                    break;
                }
            }
            if (isEqual) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型暴力方法哈希方法
时间复杂度O(n³)O(n²)
空间复杂度O(1)O(n²)

相关题目