题目
写出一个高效的算法来搜索m×n矩阵中的值，返回这个值出现的次数。
这个矩阵具有以下特性：
考虑下列矩阵：
[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]
]
给出target = 3，返回 2
要求O(m+n) 时间复杂度和O(1) 额外空间
解题
直接遍历，时间复杂度是O(MN)
public class Solution { /** * @param matrix: A list of lists of integers * @param: A number you want to search in the matrix * @return: An integer indicate the occurrence of target in the given matrix */ public int searchMatrix(int[][] matrix, int target) { // write your code here if(matrix == null) return 0; int row = matrix.length; if(row ==0) return 0; int col = matrix[0].length; int count =0; for(int i=0;i< row ;i++){ for(int j=0;j<col;j++){ if(matrix[i][j] == target) count++; } } return count; } }
题目中数组是有序的，并且每一行或者每一列的元素没有重复的
可以发现，某个数出现的次数在 0 到Min(col,row) 之间
剑指offer上好像有一个和这个很类似的题目
通过对矩阵进行划分，一次去一列
Java程序
public class Solution { /** * @param matrix: A list of lists of integers * @param: A number you want to search in the matrix * @return: An integer indicate the occurrence of target in the given matrix */ public int searchMatrix(int[][] matrix, int target) { // write your code here if(matrix == null) return 0; int row = matrix.length; if(row ==0) return 0; int col = matrix[0].length; int count =0; int i=0; int j=col-1; while(i<row && j>=0){ if(matrix[i][j] > target){ j--; }else if(matrix[i][j]< target){ i++; }else{ count++; i++; j--; } } return count; } }
Python程序
class Solution: """ @param matrix: An list of lists of integers @param target: An integer you want to search in matrix @return: An integer indicates the total occurrence of target in the given matrix """ def searchMatrix(self, matrix, target): # write your code here if matrix == None: return 0 row = len(matrix) if row ==0: return 0 col = len(matrix[0]) count = 0 i = 0 j = col - 1 while i<row and j>=0: if matrix[i][j] > target: j -=1 elif matrix[i][j] < target: i += 1 else: count += 1 i += 1 j -= 1 return count
lintcode 中等题：search a 2d matrix II 搜索二维矩阵II
原文：http://www.cnblogs.com/theskulls/p/5103450.html
