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

54 阅读 0 评论 36 点赞

我是靠谱客的博主体贴犀牛，最近开发中收集的这篇文章主要介绍1351. 统计有序矩阵中的负数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.题目

给你一个 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

2.思路

2.1 方法

二分查找法:进行查找小于0的值
情况有两种
- 中值>0的操作
  if (midValue >= 0) left = mid + 1
- 中值小于0的操作
  else并且要还要进行判断mid 是否等于 0 或者 midValue前面是否大于0这样才能进行累加为负值数，进行退出
  if(mid==0||grid(n)(mid-1)>=0) right = mid - 1
  -注意：
  将grid(n)(mid-1)>=0 这个条件放在后面否则回报指针越界当 mid= 0 时会报这个错误，
  放在后面就没问题了主要是判断有种情况找到<0的值还需要进行判断前一个值是否大于0 大于0直接进行退出，否则进行继续往前进行判断。

3.代码

object Solution {
    def countNegatives(grid: Array[Array[Int]]): Int = {
    var len = grid.length
    var n = 0
    var count = 0
    import scala.util.control.Breaks
    val loop = new Breaks
      while (n < len) {
        var left = 0
        var right = grid(n).length - 1
        loop.breakable {
        while (left <= right) {
          var mid = (right - left) / 2 + left
          var midValue = grid(n)(mid)
          if (midValue >= 0) left = mid + 1
          else {
            if(mid==0||grid(n)(mid-1)>=0){
              count = count + grid(n).length - mid
              loop.break
            }
            right = mid - 1
          }
        }
      }
        n = n + 1
    }
    count
  }
}