{"id":6327,"date":"2020-02-16T09:38:01","date_gmt":"2020-02-16T17:38:01","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6327"},"modified":"2020-02-16T09:47:55","modified_gmt":"2020-02-16T17:47:55","slug":"leetcode-1351-count-negative-numbers-in-a-sorted-matrix","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1351-count-negative-numbers-in-a-sorted-matrix\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1351. Count Negative Numbers in a Sorted Matrix"},"content":{"rendered":"\n<p>Given a&nbsp;<code>m&nbsp;* n<\/code>&nbsp;matrix&nbsp;<code>grid<\/code>&nbsp;which is sorted in non-increasing order both row-wise and column-wise.&nbsp;<\/p>\n\n\n\n<p>Return the number of&nbsp;<strong>negative<\/strong>&nbsp;numbers in&nbsp;<code>grid<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]\n<strong>Output:<\/strong> 8\n<strong>Explanation:<\/strong> There are 8 negatives number in the matrix.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[3,2],[1,0]]\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[1,-1],[-1,-1]]\n<strong>Output:<\/strong> 3\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[-1]]\n<strong>Output:<\/strong> 1\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>m == grid.length<\/code><\/li><li><code>n == grid[i].length<\/code><\/li><li><code>1 &lt;= m, n &lt;= 100<\/code><\/li><li><code>-100 &lt;= grid[i][j] &lt;= 100<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Brute Force<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(m*n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 16 ms, 10.4 MB\nclass Solution {\npublic:\n  int countNegatives(vector<vector<int>>& grid) {\n    int ans = 0;\n    for (const auto& row : grid)\n      for (const auto x : row)\n        ans += x < 0;\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Find the frontier<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(m+n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 16 ms, 10.4 MB\nclass Solution {\npublic:\n  int countNegatives(vector<vector<int>>& grid) {\n    int ans = 0;\n    int m = grid.size();\n    int n = grid[0].size();\n    int r = m - 1;\n    int c = 0;\n    while (r >= 0 && c < n) {\n      if (grid[r][c] < 0) {\n        ans += n - c;\n        --r;\n      } else {\n        ++c;\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n\n\n\n<p> <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a&nbsp;m&nbsp;* n&nbsp;matrix&nbsp;grid&nbsp;which is sorted in non-increasing order both row-wise and column-wise.&nbsp; Return the number of&nbsp;negative&nbsp;numbers in&nbsp;grid. Example 1: Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] Output: 8&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[20,8,222,216],"class_list":["post-6327","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-counting","tag-easy","tag-matrix","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6327","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6327"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6327\/revisions"}],"predecessor-version":[{"id":6329,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6327\/revisions\/6329"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6327"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6327"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6327"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}