题目
搜索二维矩阵 II
写出一个高效的算法来搜索m×n矩阵中的值,返回这个值出现的次数。
这个矩阵具有以下特性:
- 每行中的整数从左到右是排序的。
- 每一列的整数从上到下是排序的。
- 在每一行或每一列中没有重复的整数。
样例
考虑下列矩阵:
[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]
]
给出target = ,返回 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;
}
}
Java Code
题目中数组是有序的,并且每一行或者每一列的元素没有重复的
可以发现,某个数出现的次数在 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;
}}
Java Code
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
Python Code