题目1

写出一个高效的算法来搜索 m × n矩阵中的值。

这个矩阵具有以下特性：

每行中的整数从左到右是排序的。
每行的第一个数大于上一行的最后一个整数。

考虑下列矩阵：

[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
给出 target = 3，返回 true

规则
输入：int[][] 和int target
输出：boolean
case:

数组为null
二维数组为[[]]
边界

思路

这道题还是比较简单的，假设是m×n,m行n列，可以现在最后一个元素上进行二分查找，找到刚好大于target的数，然后在该行进行查找，复杂度为O(logm*logn)

public class Solution {
    /*
     * @param matrix: matrix, a list of lists of integers
     * @param target: An integer
     * @return: a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int matrxi[][],int target) {
        // write your code here
        
		int rowLen = matrxi.length;
		if(rowLen == 0){
		    return false;
		}
		int colLen = matrxi[0].length;
		if(colLen == 0){
		    return false;
		}
		int y = findY(matrxi,target,0,rowLen-1);
		if(matrxi[y][colLen-1] == target) {
			return true;
		}
		int x = findX(matrxi[y],target,0,colLen-1);
		if(x >-1) {
			return true;
		}
		return false;
	
    }
    
    /*第一个大于等于target的index*/
	public int findY(int matrxi[][],int target,int min,int max) {
		int rowLen = matrxi.length;
		int colLen = matrxi[0].length;
		int ret = rowLen-1; 
		while(true) {
			if(min > max || min < 0 || max >colLen-1) {
				return ret;
			}
			int mid = min + (max-min)/2;
			if(matrxi[mid][colLen-1] == target) {
				return mid;
			}else if(matrxi[mid][colLen-1] < target) {
				min = mid + 1;
			}else if(matrxi[mid][colLen-1] > target) {
				max = mid - 1;
				ret = mid;
			}
		}
	}
	
	public int findX(int matrxi[],int target,int min,int max) {
		int length = matrxi.length;
		while(true) {
			if(min > max || min < 0 || max > length-1) {
				return -1;
			}
			int mid = min + (max-min)/2;
			if(matrxi[mid] == target) {
				return mid;
			}else if(matrxi[mid] < target) {
				min = mid + 1;
			}else if(matrxi[mid] > target) {
				max = mid - 1;
			}
		}
	}
}

谬误
这个题目忘记考虑了边界条件，导致边界处理的不会。例如，查找每行最后一个元素时，没有考虑到不存在大于target的情况，还是要严格按照三个步骤：规则，思路，代码

题目2

在一个二维数组中，每一行都从左到右递增，每一列都从上到下递增，请完成一个函数，输入一个二维数组和一个整数，判断数组中是否含有改整数。

规则
输入：int[][] 和 int target
输出：int 出现次数
CASE：

数组为null
数组0行或0列
考虑边界条件

思路

从右上角的元素e出发，如果e大于target说明e所在的列都大于target，e移至左边一个元素；如果e小于target说明e所在的行都小于target，e向下走一步；一直走直到走到左下角。复杂度为O(m+n)

代码

public int findTarget(int matrxi[][],int target) {
	   if(matrxi == null) return false;
		int rowLen = matrxi.length;
        if(rowLen == 0)return false;
		int colLen = matrxi[0].length;
        if(colLen == 0)return false;
		int row = 0;
		int col = colLen - 1;
		while(true) {
			if(row == rowLen|| col == -1) {
				return false;
			}
			int sel = matrxi[row][col];
			if(sel == target) {
				return true;
			}else if(sel < target) {
				row ++;
			}else{ // sel > target
				col --;
			}
		}
	}

题目3

写出一个高效的算法来搜索m×n矩阵中的值，返回这个值出现的次数。

这个矩阵具有以下特性：

每行中的整数从左到右是排序的。
每一列的整数从上到下是排序的。
在每一行或每一列中没有重复的整数。

样例
考虑下列矩阵：

[

[1, 3, 5, 7],

[2, 4, 7, 8],

[3, 5, 9, 10]

]

给出target = 3，返回 2

规则
输入：int[][] 和 int target
输出：boolean
CASE：

数组为null
数组0行或0列
考虑边界条件

思路

与题目2一样，从右上角到左下角，一直查找即可

代码

public int findTarget(int matrix[][],int target) {
		   if(matrix == null) return 0;
			int rowLen = matrix.length;
	        if(rowLen == 0)return 0;
			int colLen = matrix[0].length;
	        if(colLen == 0)return 0;
			int row = 0;
			int col = colLen - 1;
			int count = 0;
			while(true) {
				if(row == rowLen|| col == -1) {
					return count;
				}
				int sel = matrix[row][col];
				if(sel == target) {
					count++;
					row ++;
					col --;
				}else if(sel < target) {
					row ++;
				}else{ // sel > target
					col --;
				}
			}
		}