欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 1351.统计有序矩阵中的负数 Java 代码 二分查找

程序员文章站 2022-07-12 08:11:34
...

LeetCode 1351.统计有序矩阵中的负数 Java 代码 二分查找

给你一个 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

进阶:你可以设计一个时间复杂度为 O(n + m) 的解决方案吗?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-negative-numbers-in-a-sorted-matrix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

  • 二分查找:

    /**
     * 二分查找
     * 时间复杂度:O(n * log m)
     * 空间复杂度:O(1)
     */
    class Solution {
        public int countNegatives(int[][] grid) {
            int res = 0;
            int m = grid[0].length, n = grid.length;
            int index = m;
            for (int i = 0; i < n; i++) {
                if (index == 0) {
                    break;
                }
                if (grid[i][index - 1] >= 0) {
                    //若最后一个行元素非负,则可跳过二分过程,提高效率
                    continue;
                }
                int left = 0, right = index;
                while (left < right) {
                    int mid = left + ((right - left) >> 1);
                    if (grid[i][mid] >= 0) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                res += (index - left) * (n - i);
                index = left;
            }
            return res;
        }
    }
    
  • 倒序遍历法(LeetCode 官方推荐):

    /**
     * 倒序遍历法:
     * 不难观察得到:每一行从前往后第一个负数的位置不断递减
     * 假设已知第 i 行的从前往后第一个负数的位置 pos_i,那么对于第 i+1 行,pos_i+1 的位置肯定是位于 [0,pos_i]
     * 所以对于第 i+1 行我们倒着从 pos_i 循环找 pos_i+1 即可,这个循环起始变量是一直在递减的。
     * 作者:LeetCode-Solution
     * 来源:力扣(LeetCode)
     * 时间复杂度:O(n + m)
     * 空间复杂度:O(1)
     */
    class Solution {
        public int countNegatives(int[][] grid) {
            int num = 0, index = grid[0].length - 1;
            int m = grid[0].length;
            for (int[] arr : grid
            ) {
                int i;
                for (i = index; i >= 0; i--) {
                    if (arr[i] >= 0) {
                        if (i + 1 < m) {
                            index = i + 1;//寻找第一个负行元素下标
                            num += m - index;
                        }
                        break;
                    }
                }
                if (i == -1) {
                    //若某行元素全为负数,则下面所有行也全为负
                    //累加即可
                    num += m;
                    index = -1;
                }
            }
            return num;
        }
    }