一题算法|统计有序矩阵中的负数
2020/3/6 8:01:36
本文主要是介绍一题算法|统计有序矩阵中的负数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
给你一个 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
提示
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 100
- -100 <= grid[i][j] <= 100
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)
作者:平头哥,学会伺机而动,实现弯道超车
这篇关于一题算法|统计有序矩阵中的负数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南