[Leetcode] 1351. Count Negative Numbers in a Sorted Matrix (Easy)

概述

題目

https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/
給定一個已排序的非遞減 m*n grid，求有多少負元素在其中

心得

有排序就有高機率是 Binary Search，哪怕此題 Easy BF 也能解

BF

思路

限制是 m, n <= 100，故暴搜一輪也頂多 10**4，可 AC

程式

class Solution(object):
    def countNegatives(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        cnt = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] < 0:
                    cnt += 1
        return cnt

一行解

class Solution(object):
    def countNegatives(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        return sum([c<0 for arr in grid for c in arr])

Complexity

Time Complexity: O(m*n)
全部走過一次

Space Complexity: O(1)
基本上無使用到額外空間

Binary Search

思路

經典的 Binary Search，只不過要注意可以多個數同時相等，故求的是最端點的

程式

class Solution(object):
    def countNegatives(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])

        def search(arr):
            def test(m):
                return arr[m] > -1
        
            l, r = 0, n
            while l<r:
                m = (l+r) // 2
                if test(m-1) and not test(m):
                    return n-m
                if not test(m):
                    r = m
                else:
                    l = m+1
            return n-l

        cnt = 0
        for i in range(m):
            cnt += search(grid[i])
        return cnt

一行解，同理但使用 bisect 函式

程式

class Solution(object):
    def countNegatives(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        return sum([bisect.bisect_right(c[::-1], -1) for c in grid])

Complexity

Time Complexity: O(m* log n)
m 排操作 log n 次

Space Complexity: O(1)
基本上無使用到額外空間

觀查

思路

透過非只有 row 有非遞減特性、col 也有，來進行 traverse

程式

class Solution(object):
    def countNegatives(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])

        col = m
        cnt = 0

        for row in grid:
            while 0 < col and row[col-1] < 0:
                col -= 1
            cnt += m-col
        return cnt