【LeetCode】 1351. Count Negative Numbers in a Sorted Matrix

Description

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.

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?

給予一個 m x n 並且欄與列都以非遞增順序排序的矩陣 grid，回傳 grid 中非負數的數量。

限制：

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

進階題：你可以找到一個 O(n + m) 的解法嗎？

Example:

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

Solution

• 先用最直覺的想法做一次：每一列都從最後面去遍歷，檢查是否為負數
  • 第一種範例 code
  • 能過，但時間複雜度為 O(m * n)
    • 最差的 case 就是全部都是負數，每一列都要跑滿

---

• 由於不只列有排序，欄其實也有排序，因此每次到下一列的時候可以不用重新從尾巴檢查，直接從上一次跑到的點檢查即可
  • 簡單來說，j 其實不需要重置
• 從矩陣的最右上開始檢查，跑負數的地方，跑到最下面一列即可
• 圖解
  • 
  • 
• 即便是全負數的 case 也只需要跑 n + m，達到 O(n + m)

Code

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int count = 0;
        for(int i = 0; i < grid.size(); i++)
            for(int j = grid[i].size() - 1; j >= 0; j--)
                count += grid[i][j] < 0;
        return count;
    }
};

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int count = 0;
        int j = 0;
        int n = grid[0].size();
        for(int i = 0; i < grid.size(); i++)
        {
            while(j != n && grid[i][n - j - 1] < 0)
            {
                j++;
            }
            count += j;
        }
                
        return count;
    }
};

tags: LeetCode C++