统计有序矩阵中的负数
解题思路：
-
第一层迭代二维数组，然后再对一维数组进行二分查找；
-
二分查找找到所有负数：
- 由于是非递增序列，则第一个数为最大值，如果第一个数小于 0，那么整个一维数组都小于 0，返回数组长度；
- 最后一个数是最小值，如果最小值大于 0 ，则整个一维数组都大于 0，返回 0 ；
- 否则一直查找，直到找到最后一个小于 0 的数的索引，当前索引为 left，返回个数=(length-1)-left+1；
图解：（二分查找）
复杂度：
-
时间复杂度：二分查找一行的时间复杂度为 logm，需要遍历 n 行，所以总时间复杂度是 O(nlogm)；
-
空间复杂度：O(1)；
代码实现：
var countNegatives = function (grid) {
if (grid.length === 0) return 0;
let row = grid.length;
let sum = 0;
for (let r = 0; r < row; r++) {
sum += search(grid[r]);
}
return sum;
};
var search = function (list) {
let left = 0;
let right = list.length - 1;
// 由于是非递减序列，第一个数最大，如果第一个数都小于 0，则整个数组都小于 0
if (list[left] < 0) return list.length;
// 由于是非递减序列，最后一个数最小，如果第一个数都大于 0，则整个数组都大于 0
if (list[right] > 0) return 0;
while (left <= right) {
let mid = left + (right - left) >> 1;
// 非递增，则左侧数最大，找小于 0 的最大数
if (list[mid] < 0) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return list.length - left;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
74.搜索二维矩阵
上一篇
评论
