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; } }
下一篇: java学习(18)-- 网络编程