[LeetCode] 1351. Count Negative Numbers in a Sorted Matrix

发布时间 2023-06-08 12:39:28作者: CNoodle

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

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 中 负数 的数目。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/count-negative-numbers-in-a-sorted-matrix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这是一道矩阵类型的题目。暴力解可以一行一行扫描;次优解可以用二分法,找到每一行的第一个负数,那么从这个位置及其右半边就都是负数;最优解的时间复杂度是 O(m + n)。

注意题目说了每一行和每一列都以非递增顺序排列,那么整个矩阵的数字应该大致长这样。

++++++
++++--
++++--
+++---
+-----
+-----

所以思路是从左下角那个点开始扫描每一行,找到每一行的第一个负数之后,就可以扫描上一行了。扫描的复杂度是O(m + n)。这个思路跟240题很像。

时间O(m + n)

空间O(1)

Java实现

 1 class Solution {
 2     public int countNegatives(int[][] grid) {
 3         int m = grid.length;
 4         int n = grid[0].length;
 5         int i = m - 1;
 6         int j = 0;
 7         int count = 0;
 8         while (i >= 0 && j < n) {
 9             if (grid[i][j] < 0) {
10                 count += n - j;
11                 i--;
12             } else {
13                 j++;
14             }
15         }
16         return count;
17     }
18 }

 

LeetCode 题目总结