1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
// 1351. Count Negative Numbers in a Sorted Matrix
#include <stdio.h>
// given an 'm x n' matrix 'grid' which is sorted in non-increasing order both
// row-wise and column-wise, return the number of negative numbers in 'grid'
void search(int **grid, int grid_size, int row, int start, int end, int *ans) {
while (start < end) {
int mid = start + (end - start) / 2;
if (grid[row][mid] >= 0) {
start = mid + 1;
if (grid[row][start] < 0) {
(*ans) += grid_size - start;
return;
}
} else {
end = mid;
}
}
}
int countNegatives(int **grid, int grid_size, int *grid_col_size) {
if (grid_size == 1 && grid_col_size[0] == 1)
return grid[0][0] < 0 ? 1 : 0;
int r_size = grid_size, c_size = grid_col_size[0], r_idx = 0, ans = 0;
for (int r = r_size - 1; r >= 0; r--) {
if (grid[r][0] >= 0) {
r_idx = r;
ans = (r_size - r_idx - 1) * c_size;
break;
}
}
for (int r = 0; r <= r_idx; r++) {
if (grid[r][c_size - 1] >= 0)
continue;
search(grid, c_size, r, 0, c_size - 1, &ans);
}
return ans;
}
int main() {
int g1[4][4] = {
{4, 3, 2, -1}, {3, 2, 1, -1}, {1, 1, -1, -2}, {-1, -1, -2, -3}};
int g2[2][2] = {{3, 2}, {1, 0}};
int gs1 = 4, gs2 = 2;
int *gcs1, *gcs2;
printf("%d\n", countNegatives(g1, gs1, gcs1)); // expect: 8
printf("%d\n", countNegatives(g2, gs2, gcs2)); // expect: 0
}
|