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直接进行退出，否则进行继续 往前进行判断。
- 中值>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
}
}
4.复杂度
- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)
