1351. Count Negative Numbers in a Sorted Matrix

Easy

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.

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

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?

解鑌

θ§£ζ³•δΈ€οΌšεΎžζœ€εΎŒδΈ€ε€‹ε…ƒη΄ ι–‹ε§‹δΈ€ε€‹ε€‹ζŸ₯ζ‰ΎοΌŒθ‹₯ι‡εˆ°ιžθ² ε…ƒη΄ οΌŒδΈ­ζ–·θ©²εˆ—ζŸ₯找。

func countNegatives(grid [][]int) int {
    res := 0

    for i := len(grid) - 1; i >= 0; i-- {
        for j := len(grid[0]) - 1; j >= 0; j-- {
            if grid[i][j] < 0 {
                res++
            } else {
                break
            }
        }
    }

    return res
}

θ§£ζ³•δΊŒοΌšBinary Search

func countNegatives(grid [][]int) int {
    res := 0

    for _, row := range grid {
        index := binarySearch(row)
        res += len(row) - index
    }

    return res
}

func binarySearch(row []int) int {
    left := 0
    right := len(row) - 1

    for left <= right {

        mid := (left + right) / 2

        if row[mid] >= 0 {
            left = mid + 1 
        } else {
            right = mid - 1
        }
    }

    //ε¦‚ζžœζ²’ζœ‰ιžθ² ηš„ζ•΄ζ•ΈοΌŒζœƒε›žε‚³ len(row)
    return left
}

Last updated