题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例:
比如在下面的二维数组中查找数字7，查找过程如下：
给定 target = 7，目标值 7 在这个数组中，返回 true 即可。
给定 target = 20，目标值 20 不在这个数组中，需要返回 false 。
题目分析
这个二维数组是有特点的：
每一行都是递增的
每一列都是递增的
首先，我们初始化一个指向矩阵右上角的 元素 。
从这个元素开始查找，如果这个元素比 target 大，则说明需要找更小的，往左走；如果这个元素比 target 小，则说明应该找更大的，往下走。
代码实现(c )
class solution {
public:
bool find(int target, vector > array) {
int rows = array.size();
int cols = array[0].size();
if(!array.empty() && rows > 0 && cols > 0){
int row = 0;
int col = cols - 1;
while(row < rows && col >= 0){
if(array[row][col] == target){
return true;
}
else if(array[row][col] > target){
--col;
}
else{
row;
}
}
}
return false;
}
};
代码实现(java)
public class solution {
public boolean find(int target, int [][] array) {
//边界条件判断
if (array == null || array.length == 0 ||
array[0] == null || array[0].length == 0)
return false;
//获取函数矩阵的行数 m 与列数 n
int m = array.length, n = array[0].length;
//初始化一开始的元素位置，这里我们设置为矩阵最右上角的元素
int i = 0, j = n - 1;
//循环遍历整个函数
while (i < m && j >= 0) {
//如果目标值小于右上角的数字，则列下标减一
if (target < array[i][j]) j--;
//如果目标值大于右上角的数字，则行下标加一
else if (target > array[i][j]) i ;
//如果相等，直接 true
else return true;
}
//循环结束后如果还没有找到目标时，返回 false
return false;
}
}
代码实现(python2.7)
# -*- coding:utf-8 -*-
class solution:
# array 二维列表
def find(self, target, array):
# write code here
rows = len(array)
cols = len(array[0])
if rows > 0 and cols > 0:
row = 0
col = cols - 1
while row < rows and col >= 0:
if target == array[row][col]:
return true
elif target < array[row][col]:
col -= 1
else:
row = 1
return false
复杂度分析
- 时间复杂度：o(n m) 。在循环语句中，除非直接返回结果，否则每一次行都会递减一次或者列都会递增一次。该矩阵共有 m 行 n 列，因此循环终止之前，循环不会运行超过 n m 次。其它的操作都是常数，所以总的时间复杂度是线性的。
- 空间复杂度：o(1)。没有使用额外的存储空间，所以它的内存占用是恒定的。