Search a 2D Matrix
Write an efficient algorithm that searches for a value in anmxnmatrix. 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]
]
Giventarget=3
, returntrue
.
这道题的解法倒是很多的,网上也有不少分析的。
比如LeetCode论坛上有分析非常仔细的,不过他好像推荐的是个O(n+m)的时间效率,这次也是个例外了,他的分析和例子都不好。
因为这道题的最优时间效率应该是O(lgm +lgn); m,n 代表行和列数,而且也没有那么复杂,不过就是考二分法的运用,能够灵活运用了做这道题不是难事,本人一次性通过。
这里是使用二分法,先列二分,然后行二分,看似复杂,其实是很简单的程序。不用看Leetcode上的那么长编大论的分析。
下面是我的程序,看起来长,其实结构很清晰,很好理解的程序。
const static int FOUND = -2;
const static int NOT_FOUND = -1;
bool searchMatrix(vector<vector<int> > &matrix, int target)
{
int found_mark = searchRow(matrix, 0, matrix.size()-1, target);
if (found_mark == NOT_FOUND) return false;
if (found_mark == FOUND) return true;
found_mark = searchCol(matrix, found_mark, 0, matrix[0].size()-1, target);
if (found_mark == NOT_FOUND) return false;
return true;
}
int searchRow(vector<vector<int> > &m, int low, int up, int tar)
{
//up = -1的时候也是等于NOT_FOUND,所以设NOT_FOUND=-1
if (low > up) return up;
int mid = low + ((up - low)>>1);
if (tar < m[mid][0])
{
return searchRow(m, low, mid-1, tar);
}
else if (m[mid][0] < tar)
{
return searchRow(m, mid+1, up, tar);
}
else return FOUND;
}
int searchCol(vector<vector<int> > &m, int row, int left, int right, int tar)
{
if (left > right) return NOT_FOUND;
int mid = left + ((right - left)>>1);
if (tar < m[row][mid])
{
return searchCol(m, row, left, mid-1, tar);
}
else if(m[row][mid] < tar)
{
return searchCol(m, row, mid+1, right, tar);
}
else return FOUND;
}
下面也看看Leetcode上的程序,也是很简单的,不过他说这个也许是面试官需要的答案?那我就怀疑了,O(lgn + lgm)比O(n+m)提高了一个档次的时间复杂度啊,当然是二分法好啦。
//属于上下行,左右列夹并追踪目标的方法,复杂度O(n+m)
bool searchMatrix2(vector<vector<int> > &matrix, int target) {
int m(matrix.size()-1), n(matrix[0].size()), k(0);
while(m>=0 && k<n){
if(matrix[m][k]==target) return true;
else if(matrix[m][k]>target) --m;
else ++k;
}
return false;
}
//2004-2-11 update
bool searchMatrix(vector<vector<int> > &matrix, int target)
{
int row = colSearch(matrix, 0, matrix.size()-1, target);
if (row == -1) return false;
return rowSearch(matrix, row, 0, matrix[row].size()-1, target);
}
int colSearch(vector<vector<int> > &m, int c1, int c2, int tar)
{
if (c1 > c2) return -1;
int mid = c1 + ((c2-c1)>>1);
if (m[mid][0]<=tar && tar<=m[mid].back()) return mid;
if (m[mid][0] < tar) return colSearch(m, mid+1, c2, tar);
if (tar < m[mid][0]) return colSearch(m, c1, mid-1, tar);
return -1;
}
bool rowSearch(vector<vector<int> > &m, int row, int r1, int r2, int tar)
{
if (r1 > r2) return false;
int mid = r1 + ((r2-r1)>>1);
if (m[row][mid] < tar) return rowSearch(m, row, mid+1, r2, tar);
if (tar < m[row][mid]) return rowSearch(m, row, r1, mid-1, tar);
return true;
}
分享到:
相关推荐
c++ c++_c++编程基础之leetcode题解第74题搜索二维矩阵
搜索二维矩阵 给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;...
leetcode上的题目,网站上测试通过,可以借鉴下
示例:现有矩阵 matrix 如下:[10, 13, 14, 17, 24],Related Topics二分查找分治算法题目代码bool searchMatr
示例:现有矩阵 matrix 如下:[10, 13, 14, 17, 24],public boolean searchMatrix(int[][] matri
304.二维区域和检索 - 矩阵不可变1.题目描述给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (r
大佬的leetcode刷题笔记(c++版本)
Python python_leetcode面试题解之第74题搜索二维矩阵_题解
leetcode-链表笔记
leetcode二维数组力码 列表 #605. 可以放置鲜花 #581。 最短的未排序连续子阵列 #566。 重塑矩阵 #624。 数组中的最大距离 #532。 数组中的 K-diff 对 #414。 第三个最大数 细节 #605. 可以放花 问题描述: 假设你有...
* [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search](https://github.com/kamyu104/LeetCode#depth-first-search) * [Backtracking]...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
二分查找Binary_Search套路和解题模板【LeetCode刷题套路教程3】
elif nums[mid] > target:elif nums[mid] 解析3:对整个矩阵做我二分查找,一共mn-1个数,根据列表长度值
1. Introduction 2. Array i. Remove Element ii. Remove Duplicates from Sorted Array iii.... Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. Find Peak Element
lru ...二分搜索/非排序二分 Find Peak Element First Bad Version Valid Perfect Square 二叉树查找/BST查找 Closest Binary Search Tree Value 二叉树查找/二叉树第K个 Kth Smallest Element In A
LeetCode 刷题笔记
leetcodebook_leetcode 1~400知识点&题型总结&leetcode对应题表