给你一个 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
提示
leetcode 第1351题,从题目中我们可以知道,矩阵是不确定的多维数组,并且每一行和每一列的数据以非递增的顺序排列,也就是对每一行来说后面的数一定不会比前面的大,对于每一列来说下面的数不会比上面的大,这对我们解题非常有帮助。
这题有两种解法,第一种就是万能的暴力解法,另一种是利用利用二分法快速查到到每一行第一个小于 0 的元素,再结合上面的特性,就可以快速的找出每一行中的负数。
暴力破解法直接两层循环遍历矩阵,写法比较简单。虽然是暴力解法,但是如果结合一些小技巧,也可以快速得出矩阵中的负数。
1、解题代码:
class Solution { public int countNegatives(int[][] grid) { // 负数的个数 int num = 0; // 遍历行 for (int i = 0; i < grid.length; i++) { // 判断每一行的第一个元素是否小于0,这个可以减少很多遍历 if (grid[i][0] < 0) { num += (grid.length - i) * grid[0].length; break; } // 在剩下的元素中找出第一个小于 0 的,后面的元素都小于 0 for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] < 0) { num += (grid[0].length - j); break; } } } return num; } }
复杂度分析
时间复杂度:需要遍历一次数组,所以时间复杂度是O(N^2)
空间复杂度:在遍历的过程中只是用到了一个临时变量 num,所以空间复杂度为O(1)
由题目可以知道,每一行的元素是有序的,所以我们可以使用二分查找法来快速查找到每一行第一个小于 0 的元素。二分查找在理论情况下来比直接一个一个遍历比较要快很多,特别是大数据量的情况下。二分查找有递归和非递归两种实现方式,这里我才用非递归的方式,如果您对二分查找不熟悉,可以查询相关资料。
1、解题代码
class Solution { int num = 0; // 遍历行 for (int[] grid : grids) { // 二分查找 low 左边下标 high 右边下边 pos 第一个小于0 的元素下标 int low = 0, high = grid.length - 1, pos = -1; while (low <= high) { if (grid[0] < 0) { pos = 0; break; } int mid = low + ((high - low) >> 1); if (grid[mid] < 0) { pos = mid; high = mid - 1; } else low = mid + 1; } // 如果该行没有找到小于0 的元素,不统计 if (pos >= 0) num += grid.length - pos; } return num ; }
复杂度分析
时间复杂度:需要遍历一次数组,所以时间复杂度是O(N)
空间复杂度:跟暴力破解一样,没有使用新的集合,所以空间复杂度为O(1)
以上就是我的两种解法,不知道小伙伴们是如何解这题的,欢迎在留言区亮出你的解法。
互联网平头哥(id:pingtouge_java)
作者:平头哥,学会伺机而动,实现弯道超车