1582. 二进制矩阵中的特殊位置

🟢   🔖  数组 矩阵  🔗 力扣 LeetCode

题目

Given an m x n binary matrix mat, return the number of special positions inmat.

A position (i, j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

Example 1:

Input: mat = [[1,0,0],[0,0,1],[1,0,0]]

Output: 1

Explanation: (1, 2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.

Example 2:

Input: mat = [[1,0,0],[0,1,0],[0,0,1]]

Output: 3

Explanation: (0, 0), (1, 1) and (2, 2) are special positions.

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• mat[i][j] is either 0 or 1.

题目大意

给定一个 m x n 的二进制矩阵 mat，返回矩阵 mat 中特殊位置的数量。

如果位置 (i, j) 满足 mat[i][j] == 1 并且行 i 与列 j 中的所有其他元素都是 0（行和列的下标从 0 开始计数），那么它被称为特殊 位置。

示例 1：

输入： mat = [[1,0,0],[0,0,1],[1,0,0]]

输出： 1

解释： 位置 (1, 2) 是一个特殊位置，因为 mat[1][2] == 1 且第 1 行和第 2 列的其他所有元素都是 0。

示例 2：

输入： mat = [[1,0,0],[0,1,0],[0,0,1]]

输出： 3

解释： 位置 (0, 0)，(1, 1) 和 (2, 2) 都是特殊位置。

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• mat[i][j] 是 0 或 1。

解题思路

1. 统计行和列的 1 的个数：

   • 使用两个数组 rowCount 和 colCount 分别记录每行和每列中 1 的个数。
   • 遍历整个矩阵 mat：
     • 如果元素值为 1，则增加对应行和列计数。

2. 判断特殊位置：

   • 再次遍历矩阵：
     • 如果当前位置 mat[i][j] 为 1 且满足：
       • 当前行的计数 rowCount[i] 为 1；
       • 当前列的计数 colCount[j] 为 1；
     • 则当前位置为特殊位置，结果 res 增加 1。

3. 返回结果：

   • 返回统计得到的特殊位置的数量 res。

复杂度分析

• 时间复杂度：O(m * n)，其中 m 和 n 分别是矩阵的行数和列数，两次遍历整个矩阵。
• 空间复杂度：O(m + n)，需要两个数组 rowCount 和 colCount 来记录行和列的计数。

代码

/**
 * @param {number[][]} mat
 * @return {number}
 */
var numSpecial = function (mat) {
	const m = mat.length;
	const n = mat[0].length;

	// 统计每行和每列中 1 的个数
	const rowCount = new Array(m).fill(0);
	const colCount = new Array(n).fill(0);

	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (mat[i][j] === 1) {
				rowCount[i]++;
				colCount[j]++;
			}
		}
	}

	// 判断特殊位置
	let res = 0;
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (mat[i][j] === 1 && rowCount[i] === 1 && colCount[j] === 1) {
				res++;
			}
		}
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
2482	行和列中一和零的差值		数组 矩阵 模拟	🟠	🀄️ 🔗