1351.Count Negative Numbers in a Sorted Matrix

tags: `Easy`,`Array`,`Binary Search`,`Matrix`

1351. Count Negative Numbers in a Sorted Matrix

題目描述

Given a 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.

範例

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]]
Output: 0

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

Follow up: Could you find an

O (n + m)

solution?

解答

C++

Linear search

















class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        ios_base::sync_with_stdio(0), cin.tie(0);
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;
        for (int r = 0; r < m; r ++) {
            for (int c = 0; c < n; c ++) {
                if (grid[r][c] < 0) {
                    ans ++;
                }
            }
        }
        return ans;
    }
};

Jerry Wu8 June, 2023

Binary search













class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        ios_base::sync_with_stdio(0), cin.tie(0);
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;
        for (const auto row : grid) {
            ans += upper_bound(row.rbegin(), row.rend(), -1) - row.rbegin();
        }
        return ans;
    }
};

Jerry Wu8 June, 2023

C#


















public class Solution {
    public int CountNegatives(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        
        int count = 0;
        int rowCount = 0;
        for (int row = 0; row < m; row++) {
            for (int col = n - 1 - rowCount; col >= 0; col--) {
                if (grid[row][col] >= 0) break;
                rowCount++;
            }
            count += rowCount;
        } 

        return count;
    }
}

JimJun 8, 2023

Python



class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        return len([elem for arr in grid for elem in arr if elem < 0])

Ron ChenTue, Jun 8, 2023

Java

我寫的版本
















class Solution {
    public int countNegatives(int[][] grid) {
        List<List<Integer>> list = Arrays.stream(grid)
                .map(row -> Arrays.stream(row).boxed().collect(Collectors.toList()))
                .collect(Collectors.toList());

        int res = 0;
        for (List<Integer> sublist : list) {
            for (int num : sublist) {
                if(num < 0) res++;
            }
        }

        return res;
    }
}

ChatGPT 寫的版本








class Solution {
    public int countNegatives(int[][] grid) {
        return (int) Arrays.stream(grid)
                .flatMapToInt(Arrays::stream)
                .filter(num -> num < 0)
                .count();
    }
}