链接：https://leetcode-cn.com/problems/count-negative-numbers-in-a-sorted-matrix/
文章图片
https://leetcode-cn.com/problems/count-negative-numbers-in-a-sorted-matrix/
【leetcode|Leetcode二分查找12:1351. 统计有序矩阵中的负数】题意就是给一个n*m的矩阵，让你找出里面有多少个负数。
一.最容易想的暴力枚举 遍历二维数组就需要一个二重循环。
- 时间复杂度：O(nm)，即矩阵元素的总个数。
- 空间复杂度：O(1)。
class Solution {
public:
int countNegatives(vector>& nums) {
long long ans=0;
//防止爆int
int n=nums.size();
int m=nums[0].size();
for(int i=0;
i 二.二分(因为已经数组已经被排序) 注意到题目中给了一个性质，即矩阵中的元素无论是按行还是按列，都以非递增顺序排列，可以考虑把这个性质利用起来优化暴力。我们通过二分查找可以找到每一行中从前往后的第一个负数，那么这个位置之后到这一行的末尾里所有的数必然是负数了，可以直接统计。
分为三步：
一.遍历矩阵的每一行
二.二分查找到该行从前往后的第一个负数。如果第i行对应的位置是
文章图片
，那么这一行对答案的贡献就是m-
文章图片
。
三.答案就是从0到n-1行的m-
文章图片
累计值。
class Solution {
public:
int countNegatives(vector>& nums) {
long long ans=0;
for (auto x:nums){
int l=0,r=(int)x.size()-1,pos=-1;
while (l<=r){
int mid=l+((r-l)/2);
if (x[mid]<0){
pos=mid;
r=mid-1;
}
else l=mid+1;
}
if (~pos) ans+=(int)x.size()-pos;
// pos=-1表示这一行全是>=0的数，不能统计
}
return ans;
}
};
推荐阅读
- 动态规划|AcWing 271. 杨老师的照相排列（简单DP）+ 十一届蓝桥杯B组试题E--矩阵
- 哈希|Leetcode二分查找11:1346. 检查整数及其两倍数是否存在
- 数据结构与算法|数据结构与性质(2)栈(stack)基础板子
- leetcode|Leetcode二分查找4:69. x 的平方根
- c++|Leetcode二分查找9:744. 寻找比目标字母大的最小字母
- 蓝桥杯练习题|蓝桥杯 基础训练--阶乘计算（高精度）、高精度加法
- 蓝桥杯练习题|分解质因数
- 蓝桥杯练习题|【无标题】
- LeetCode|Java实现 LeetCode 704 二分查找（二分法）