1351. 统计有序矩阵中的负数

🟢   🔖  数组 二分查找 矩阵  🔗 力扣 LeetCode

题目

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number ofnegative numbers ingrid.

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]

Output: 8

Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]]

Output: 0

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

Follow up: Could you find an O(n + m) solution?

题目大意

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非严格递减顺序排列。 请你统计并返回 grid 中 负数 的数目。

示例 1：

输入： grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]

输出： 8

解释： 矩阵中共有 8 个负数。

示例 2：

输入： grid = [[3,2],[1,0]]

输出： 0

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

进阶： 你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？

解题思路

思路一：逐行二分查找

1. 对每一行使用二分查找，找到第一个负数的位置。
2. 由行的性质可知，该位置右侧的所有元素都是负数。
3. 累计每行的负数数量，最终返回总数。

复杂度分析：

• 时间复杂度：O(m log n)，其中 m 是行数，n 是列数。每一行执行一次二分查找，耗时 O(log n)，共 m 行。
• 空间复杂度：O(1)，仅使用了常量额外空间。

---

思路二：矩阵逆向遍历

1. 从矩阵的右上角开始移动（row = 0，col = n - 1）：
   • 如果当前位置是正数，向下移动（增加行索引）。
   • 如果当前位置是负数，向左移动（减少列索引）。
2. 每次遇到负数时，说明当前列从该行往下的所有元素都是负数。
3. 累计负数的个数。

复杂度分析：

• 时间复杂度：O(m + n)，最多遍历 m + n 次。
• 空间复杂度：O(1)，仅使用了常量额外空间。

代码

逐行二分查找

/**
 * @param {number[][]} grid
 * @return {number}
 */
var countNegatives = function (grid) {
	let count = 0;
	// 逐行二分查找
	for (let row of grid) {
		let left = 0,
			right = row.length - 1;
		while (left <= right) {
			let mid = Math.floor((left + right) / 2);
			if (row[mid] < 0) {
				right = mid - 1; // 负数在左侧
			} else {
				left = mid + 1; // 正数在右侧
			}
		}
		// 剩下的负数数量是从 left 到行尾的元素
		count += row.length - left;
	}
	return count;
};

矩阵逆向遍历

/**
 * @param {number[][]} grid
 * @return {number}
 */
var countNegatives = function (grid) {
	const m = grid.length;
	const n = grid[0].length;
	let total = 0;
	let row = 0,
		col = n - 1;
	while (row < m && col >= 0) {
		if (grid[row][col] < 0) {
			// 当前列从 row 到底部的所有元素都是负数
			total += m - row;
			col--; // 左移列
		} else {
			row++; // 下移行
		}
	}
	return total;
};

相关题目

题号	标题	题解	标签	难度	力扣
2529	正整数和负整数的最大计数		数组 二分查找 计数	🟢	🀄️ 🔗