[LeetCode] 1351. Count Negative Numbers in a Sorted Matrix

1351. Count Negative Numbers in a Sorted Matrix

문제는 매우 쉽다!!

---

코드

시간복잡도 : O(n * m)

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        ans = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] < 0:
                    ans += 1
        return ans

시간복잡도 : O(2m * log n)

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m = len(grid)
        ans = 0
        for r in range(m):
            grid[r].sort()
            ans += bisect.bisect_left(grid[r], 0)
        return ans

시간복잡도 : O(m * log n)

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        n = len(grid[0])
        ans = 0
            for row in grid:
            l, r = 0, n
            while l < r:
                c = (l + r) // 2
                if row[c] >= 0:
                    l = c + 1
                else:
                    r = c
            ans += n - l
        return ans

Could you find an O(n + m) solution?

문제를 잘 읽어봤다면 행과 열이 모두 내림차순 정렬이 되어 있다는 것을 알았을것이다.(난 몰랐음)
그렇기에 왼쪽 밑에서 출발하여 오른쪽 위까지 확인하면 O(n + m)가능하다.
즉, 현재 위치가 음수이면 현재위치부터 배열 끝까지 음수

시간복잡도 : O(n + m)

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        m, n = len(grid) - 1, 0
        ans = 0
        while m >= 0 and n < len(grid[0]):
            if grid[m][n] >= 0:
                n += 1
            else:
                ans += len(grid[0]) - n
                m -= 1

        return ans

테스트해보니 O(m * logn)과 O(n + m)의 속도차이가 얼마 나지 않았다.

O(n log m) vs O(n+m) - which is better?

n의 크기가 매우 크다면 logn이 작아지기 때문에 n + m보다 더 빠르다고 한다.
지금 이 문제는 m과 n의 크기가 100개밖에 안되기 때문에 별 의미가 없다.

여러 방식으로 풀어볼 수 있어 재미있었던 문제