当前位置:网站首页>LeetCode 1351、统计有序矩阵中的负数
LeetCode 1351、统计有序矩阵中的负数
2022-04-23 20:23:00 【亡于灬】
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)分析
遍历。
- 遍历到每一行第一个元素,判断正负,若为负数,结果直接加上一行的长度与剩余行数的乘积,退出遍历;
- 若当前行第一个元素为非负,遍历该行,判断每一个元素的正负,若为负数,结果加上当前行剩余元素数量,退出当前行的遍历。
行遍历,行内二分。
- 遍历到每一行第一个元素,判断正负,若为负数,结果直接加上一行的长度与剩余行数的乘积,退出遍历;
- 若当前行第一个元素为非负,通过二分找到第一个负数的位置,结果加上当前行剩余元素数量,退出当前行的搜索。
3)C++
代码
遍历
class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
int res=0;
for(int i=0;i<grid.size();i++){
if(grid[i][0]>=0){
for(int j=0;j<grid[0].size();j++){
if(grid[i][j]<0){
res+=grid[0].size()-j;
break;
}
}
}
else{
res+=grid[0].size()*(grid.size()-i);
break;
}
}
return res;
}
};
行遍历,行内二分。
class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
int res=0;
int m=grid.size();
int n=grid[0].size();
for(int i=0;i<m;i++){
if(grid[i][0]>=0){
if(grid[i][n-1]>=0)
continue;
else{
int left=0;
int right=n-1;
while(left<=right){
int mid=(left+right)/2;
if(grid[i][mid]>=0)
left=mid+1;
else
right=mid-1;
}
res+=grid[i][left]<0?n-left:0;
}
}
else{
res+=n*(m-i);
break;
}
}
return res;
}
};
版权声明
本文为[亡于灬]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_38342510/article/details/124360306
边栏推荐
- Mathematical modeling column | Part 5: MATLAB optimization model solving method (Part I): Standard Model
- How about CICC fortune? Is it safe to open an account
- WordPress plug-in: WP CHINA Yes solution to slow domestic access to the official website
- Livego + ffmpeg + RTMP + flvjs to realize live video
- An error is reported in the initialization metadata of the dolphin scheduler -- it turns out that there is a special symbol in the password. "$“
- Identification of bolt points in aerial photography based on perception
- 三十一. `prototype`显示原型属性和`__proto__`隐式原型属性
- [PTA] get rid of singles
- [target tracking] pedestrian attitude recognition based on frame difference method combined with Kalman filter, with matlab code
- 考研英语唐叔的语法课笔记
猜你喜欢
DNS cloud school | analysis of hidden tunnel attacks in the hidden corner of DNS
DNS cloud school rising posture! Three advanced uses of authoritative DNS
[PTA] l1-002 printing hourglass
An error is reported when sqoop imports data from Mysql to HDFS: sqlexception in nextkeyvalue
DNS cloud school | quickly locate DNS resolution exceptions and keep these four DNS status codes in mind
How can matlab obtain the truncated image in trainingimagelabeler
Three. Based on ply format point cloud voxel model JS upload interface writing
Error reported by Azkaban: Azkaban jobExecutor. utils. process. ProcessFailureException: Process exited with code 127
【PTA】L1-002 打印沙漏
Customize timeline component styles
随机推荐
Cadence Orcad Capture CIS更换元器件之Link Database 功能介绍图文教程及视频演示
考研英语唐叔的语法课笔记
How to protect ECs from hacker attacks?
selenium.common.exceptions.WebDriverException: Message: ‘chromedriver‘ executable needs to be in PAT
Scrapy教程 - (2)寫一個簡單爬蟲
The R language uses the timeroc package to calculate the multi time AUC value of survival data without competitive risk, and uses the confint function to calculate the confidence interval value of mul
Why does ES6 need to introduce map when JS already has object type
Commit and rollback in DCL of 16 MySQL
网络通信基础(局域网、广域网、IP地址、端口号、协议、封装、分用)
XXXI` Prototype ` displays prototype properties and`__ proto__` Implicit prototype properties
Redis的安装(CentOS7命令行安装)
[PTA] l1-002 printing hourglass
Error reported by Azkaban: Azkaban jobExecutor. utils. process. ProcessFailureException: Process exited with code 127
Local call feign interface message 404
上海回应“面粉官网是非法网站”:疏于运维被“黑”,警方已立案
PCL点云处理之直线与平面的交点计算(五十三)
Scripy tutorial - (2) write a simple crawler
【目标跟踪】基于帧差法结合卡尔曼滤波实现行人姿态识别附matlab代码
Confusion about thread blocking after calling the read () method of wrapper flow
Shanghai responded that "flour official website is an illegal website": neglect of operation and maintenance has been "hacked", and the police have filed a case