leetcode——Search a 2D Matrix 二维有序数组查找(AC)

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;
}
};
上一篇:xcode UIButton创建、监听按钮点击、自定义按钮 、状态 、内边距


下一篇:第二次作业-分布式版本控制系统Git的安装与使用