Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/description/
: 1351. Count Negative Numbers in a Sorted Matrix
: 給你一個排序好的 Matrix，找出該 Matrix 有幾個非正整數。
: 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

推 pandix: 這樣跑到n^2了
推 Che31128: 這題遍尋有辦法跑n嗎
推 NTHUlagka: 這題應該能O(min(m,n)) 因為他rows column都是有序的
1.可以從左下開始找，如果左下是正數的話上面的行都不用看了。

Java Code：
--------------------------------------------------------
class Solution {
    public int countNegatives(int[][] grid) {
        int count = 0;
        int n = grid.length;
        int m = grid[0] .length;
        int row = n - 1;
        int col = 0;
        while (col < m && row >= 0) {
            if (grid[row][col] < 0) {
                count += m - col;
                row--;
            } else {
                col++;
            }
        }
        return count;
    }
}
--------------------------------------------------------

https://i.imgur.com/8ZXLj1O.jpeg

--
https://i.imgur.com/3e5CZfj.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1686199575.A.F3D.html
→ wwndbk: 大師
→ JIWP: 大師
推 NTHUlagka: XD我原本的想法不是這樣做 但你這個比我的更好更簡潔
→ NTHUlagka: 大師
推 Che31128: 大師