X

LEETCODE 1351. Count Negative Numbers in a Sorted Matrix 解题思路分析

题目大意:

统计有序矩阵中的负数

给你一个 m * n 的矩阵 grid,矩阵中的元素无论是按行还是按列,都以非递增顺序排列。

请你统计并返回 grid负数 的数目。

示例 1:

输入:grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出:8
解释:矩阵中共有 8 个负数。

示例 2:

输入:grid = [[3,2],[1,0]]
输出:0

示例 3:

输入:grid = [[1,-1],[-1,-1]]
输出:3

示例 4:

输入:grid = [[-1]]
输出:1

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • -100 <= grid[i][j] <= 100

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1351

解题思路分析:

我们之前的文章讲过,看到这种横竖都排列好的矩阵问题,应该下意识想到从左下角开始遍历数组。也就是从矩阵最后一行的首列开始遍历,如果当前数字不是负数,向右移动一格,反之如果当前数是负数,说明该数字之后都是负数,累加当前列到尾列的个数到返回结果。然后向上移动一格,继续重复上述步骤,直到当前位置超出矩阵范围为止。

实现代码:

public int countNegatives(int[][] grid) {
    // 初始化当前行为最后一行
    int row = grid.length-1;
    // 初始化当前列为第一列
    int col = 0;
    // 返回结果
    int res=0;
    // 当位置没有超出矩阵范围时循环
    while(row>=0&&col<grid[0].length){
        // 如果当前数字小于0
        if(grid[row][col]<0){
            // 累加当前列到尾列的数量
            res+=grid[0].length-col;
            // 同时向上移动一格
            row--;
        }else{
            // 反之向有移动一格
            col++;
        }
    }
    return res;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Count Negative Numbers in a Sorted Matrix.

Memory Usage: 41.8 MB, less than 100.00% of Java online submissions for Count Negative Numbers in a Sorted Matrix.

进阶:另外本题可以使用二分查找来做进一步的优化,我们在当前列到尾列的范围内使用二分查找找到第一个负数的位置,这样可以优化横向移动的遍历时间。

二分查找实现代码:

public int countNegatives(int[][] grid) {
    int row = grid.length-1;
    int col = 0;
    int res=0;
    while(row>=0&&col<grid[0].length){
        int l=col,r=grid[0].length-1;
        while(l<=r){
            int mid = (l+r)/2;
            if(grid[row][mid]<0){
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        if(l<grid[0].length){
            res+=grid[0].length-l;
        }
        row--;
    }
    return res;
}

本解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Count Negative Numbers in a Sorted Matrix.

Memory Usage: 41.6 MB, less than 100.00% of Java online submissions for Count Negative Numbers in a Sorted Matrix.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1351-count-negative-numbers-in-a-sorted-matrix-解题思路分析/
Categories: leetcode
kwantong: