题目描述
给你一个 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.lengthn == grid[i].length1 <= m, n <= 100-100 <= grid[i][j] <= 100
进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？
解法
方法一：从左下角或右上角开始遍历
根据其行列都以非递增顺序排列的特点，可以从左下角开始往右上方向遍历。
当遇到负数时，说明这一行从当前位置开始往右的所有元素均为负数，我们将答案加上这一行剩余的元素个数，即 $n - j$，并且向上移动一行，即 $i \leftarrow i - 1$。否则，向右移动一列，即 $j \leftarrow j + 1$。
遍历结束，返回答案。
时间复杂度 $O(m + n)$，其中 $m$ 和 $n$ 分别为矩阵的行数和列数。空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
i, j = m - 1, 0
ans = 0
while i >= 0 and j < n:
if grid[i][j] < 0:
ans += n - j
i -= 1
else:
j += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public int countNegatives(int[][] grid) {
int m = grid.length, n = grid[0].length;
int ans = 0;
for (int i = m - 1, j = 0; i >= 0 && j < n;) {
if (grid[i][j] < 0) {
ans += n - j;
--i;
} else {
++j;
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int ans = 0;
for (int i = m - 1, j = 0; i >= 0 && j < n;) {
if (grid[i][j] < 0) {
ans += n - j;
--i;
} else
++j;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | func countNegatives(grid [][]int) int {
m, n := len(grid), len(grid[0])
ans := 0
for i, j := m-1, 0; i >= 0 && j < n; {
if grid[i][j] < 0 {
ans += n - j
i--
} else {
j++
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | function countNegatives(grid: number[][]): number {
const m = grid.length,
n = grid[0].length;
let ans = 0;
for (let i = m - 1, j = 0; i >= 0 && j < n; ) {
if (grid[i][j] < 0) {
ans += n - j;
--i;
} else {
++j;
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | impl Solution {
pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
let n = grid[0].len();
grid.into_iter()
.map(|nums| {
let mut left = 0;
let mut right = n;
while left < right {
let mid = left + (right - left) / 2;
if nums[mid] >= 0 {
left = mid + 1;
} else {
right = mid;
}
}
(n - left) as i32
})
.sum()
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | /**
* @param {number[][]} grid
* @return {number}
*/
var countNegatives = function (grid) {
const m = grid.length,
n = grid[0].length;
let ans = 0;
for (let i = m - 1, j = 0; i >= 0 && j < n; ) {
if (grid[i][j] < 0) {
ans += n - j;
--i;
} else {
++j;
}
}
return ans;
};
|
方法二：二分查找
遍历每一行，二分查找每一行第一个小于 $0$ 的位置，从该位置开始往右的所有元素均为负数，累加负数个数到答案中。
遍历结束，返回答案。
时间复杂度 $O(m \times \log n)$，其中 $m$ 和 $n$ 分别为矩阵的行数和列数。空间复杂度 $O(1)$。
| class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
return sum(bisect_left(row[::-1], 0) for row in grid)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public int countNegatives(int[][] grid) {
int ans = 0;
int n = grid[0].length;
for (int[] row : grid) {
int left = 0, right = n;
while (left < right) {
int mid = (left + right) >> 1;
if (row[mid] < 0) {
right = mid;
} else {
left = mid + 1;
}
}
ans += n - left;
}
return ans;
}
}
|
| class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
int ans = 0;
for (auto& row : grid) {
ans += lower_bound(row.rbegin(), row.rend(), 0) - row.rbegin();
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | func countNegatives(grid [][]int) int {
ans, n := 0, len(grid[0])
for _, row := range grid {
left, right := 0, n
for left < right {
mid := (left + right) >> 1
if row[mid] < 0 {
right = mid
} else {
left = mid + 1
}
}
ans += n - left
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | function countNegatives(grid: number[][]): number {
const n = grid[0].length;
let ans = 0;
for (let row of grid) {
let left = 0,
right = n;
while (left < right) {
const mid = (left + right) >> 1;
if (row[mid] < 0) {
right = mid;
} else {
left = mid + 1;
}
}
ans += n - left;
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | impl Solution {
pub fn count_negatives(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut i = m;
let mut j = 0;
let mut res = 0;
while i > 0 && j < n {
if grid[i - 1][j] >= 0 {
j += 1;
} else {
res += n - j;
i -= 1;
}
}
res as i32
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | /**
* @param {number[][]} grid
* @return {number}
*/
var countNegatives = function (grid) {
const n = grid[0].length;
let ans = 0;
for (let row of grid) {
let left = 0,
right = n;
while (left < right) {
const mid = (left + right) >> 1;
if (row[mid] < 0) {
right = mid;
} else {
left = mid + 1;
}
}
ans += n - left;
}
return ans;
};
|