1351. 统计有序矩阵中的负数
给你一个 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
示例 3：
输入：grid = [[1,-1],[-1,-1]]
输出：3
示例 4：
输入：grid = [[-1]]
输出：1
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 100-100 <= grid[i][j] <= 100
进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？
题解
我的吭哧憋屈调出来的题解：
思路主要是想利用题目中，横纵都有序的条件，
- 从矩阵左上角
出发，先向右，遇到第一个负数
，那么该列
位置以下全都是负数，
- 且，下一行的首个负数的横坐标，一定在
的闭区间中，此时从
往左倒着寻找即可。
- 在上述遍历过程中，记录下每一行的第一个负数的坐标，遍历结束后，根据纵坐标可得每行的负数个数，累加各行可得答案
- 回顾：这样的思路相当于把整个矩阵展开成了一维，又好像不是。。。
image.png
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
x,y,column, row = 0, 0, len(grid[0]), len(grid)
firstNegativePos = []
while x < row and y < column and y >= 0:
if grid[x][y] >= 0:
if y == column - 1:
x += 1
y = 0
else:
y += 1
else:
firstNegativePos.append((x,y)) # 记录下本行第一个负数位置
x += 1
while y > 0 and x < row and grid[x][y] <= 0:
y -= 1
print(firstNegativePos)
cnt = 0
for pos in firstNegativePos: # 根据每一行的首个负数位置，计算改行负数总数量；各行累加即可得到矩阵负数总数
cnt = cnt + column - pos[1]
return cnt
评论区有位同学的思路和我异曲同工 [C++] 双指针简单做法 - 统计有序矩阵中的负数 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size(), i = 0, j = m;
int ans = 0;
while(i < n && j >= 0){
j--;
if(i >= n || j < 0) break;
while(i < n && grid[i][j] >= 0) i++;
ans += n - i;
}
return ans;
}
};
作者：answerer
链接：https://leetcode-cn.com/problems/count-negative-numbers-in-a-sorted-matrix/solution/c-shuang-zhi-zhen-jian-dan-zuo-fa-by-ans-vplz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
好吧，我的方法原来是双指针？？？
官方题解
统计有序矩阵中的负数 - 统计有序矩阵中的负数 - 力扣（LeetCode） (leetcode-cn.com)
官方题解有四种，一是暴力，而是二分的暴力，三是分治【我看不懂。。。】，四是倒序，和我的方法类似
class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
int num=0,m=(int)grid[0].size(),pos=(int)grid[0].size()-1;
for (auto x:grid){
int i;
for (i=pos;i>=0;--i){
if (x[i]>=0){
if (i+1<m){
pos=i+1;
num+=m-pos;
}
break;
}
}
if (i==-1){
num+=m;
pos=-1;
}
}
return num;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/count-negative-numbers-in-a-sorted-matrix/solution/tong-ji-you-xu-ju-zhen-zhong-de-fu-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
