leetcode——Search a 2D Matrix 二维有序数组查找(AC)
2023-09-14 09:08:14 时间
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
Given target = 3
, return true
.
假设直接对矩阵元素进行二分查找的话,时间复杂度是O(m*n),事实上非常easy想到先通过查找找到相应可能存在于哪一行,然后再在那行中查找是否存在,採用最简单的直接查找这样时间复杂度仅有O(m+n),假设这两次查找再分别採用二分查找的话,时间复杂度更能够减少到O(logm+logn),以下是O(m+n)的代码:
class Solution { public: bool searchMatrix(vector<vector<int> > &matrix, int target) { if(matrix.empty()) return false; int m = matrix.size(); int n = matrix[0].size(); int i = 0, j=0; while(i<m && target>=matrix[i][0]) i++; i--; if(i==-1) return false; while(j<n) { if(target == matrix[i][j]) return true; else j++; } return false; } };
相关文章
- ☆打卡算法☆LeetCode 206. 反转链表 算法解析
- ☆打卡算法☆LeetCode 209. 长度最小的子数组 算法解析
- <leetcode刷题-数组>删除排序数组中的重复项
- <leetcode刷题-数组> 【双指针】旋转数组
- Leetcode 差分数组的应用「建议收藏」
- LeetCode题解——和为 k 的子数组
- leetcode-189. 旋转数组
- LeetCode 237. 删除链表中的节点
- LeetCode 1051. 高度检查器
- LeetCode 561. 数组拆分 I
- LeetCode 1389. 按既定顺序创建目标数组
- LeetCode 387. 字符串中的第一个唯一字符
- LeetCode 2195. 向数组中追加 K 个整数(贪心)
- JavaScript刷LeetCode拿offer-二叉树层序遍历篇
- leetcode 54. 螺旋矩阵 js高效实现
- LeetCode | 删除链表的倒数第 N 个结点
- JavaScript刷LeetCode贪心算法篇
- LeetCode-分治
- LeetCode-448-找到所有数组中消失的数字
- 每日一道leetcode:1. 两数之和
- leetcode:数组中的第K个最大元素