LeetCode 2352. 相等行列对

1. 题目

给你一个下标从 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]
1
2
3
4

示例 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].length
1 <= n <= 200
1 <= grid[i][j] <= 10^5
1
2
3
4
5
6
7
8
9
10
11

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/equal-row-and-column-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 暴力，找到首列和首行相同的数，然后再进行比较

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = defaultdict(list) # v: [idx ]
        for i in range(n):
            m[grid[0][i]].append(i)
        def same(x, y):
            for i in range(n):
                if grid[x][i] != grid[i][y]:
                    return False
            return True
        ans = 0
        for i in range(n):
            for j in m[grid[i][0]]:
                if same(i, j):
                    ans += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1976 ms 18.6 MB Python3

• 更优的做法，转置后得到的新矩阵 跟原来的进行比较

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        n = len(grid)
        g2 = [[0 for i in range(n)] for j in range(n)]
        for i in range(n):
            for j in range(n):
                g2[i][j] = grid[j][i]
        ans = 0
        for i in range(n):
            for j in range(n):
                if g2[i] == grid[j]:
                    ans += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

404 ms 18.5 MB Python3

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！