38 · Search a 2D Matrix II - LintCode

# Description

Write an efficient algorithm that searches for a value in an m x n matrix, return The number of occurrence of it.

This matrix has the following properties:

# Example

Example 1:

Input:

matrix = [[3,4]]
target = 3

Output:

Explanation:

There is only one 3 in the matrix.

Example 2:

Input:

matrix = [
      [1, 3, 5, 7],
      [2, 4, 7, 8],
      [3, 5, 9, 10]
    ]
target = 3

Output:

Explanation:

There are two 3 in the matrix.

O(m+n) time and O(1) extra space

可以從矩陣的右上角 (0, row - 1) 開始搜，直到左下角結束
要注意的是搜索範圍不能越界，找到一個 target 就 count + 1

	public class Solution {
	/**
	* @param matrix: A list of lists of integers
	* @param target: An integer you want to search in matrix
	* @return: An integer indicate the total occurrence of target in the given matrix
	*/
	public int searchMatrix(int[][] matrix, int target) {
	if (matrix == null \|\| matrix.length == 0 \|\| matrix[0].length == 0 \|\| matrix[0] == null) {
	return 0;
	}

	int rows = matrix.length;
	int cols = matrix[0].length;
	int x = 0;
	int y = cols - 1;
	int count = 0;
	while (x < rows && y >= 0) {
	if (matrix[x][y] < target) {
	x++;
	} else if (matrix[x][y] > target) {
	y--;
	} else {
	count++;
	x++;
	y--;
	}

	}
	return count;
	}
	}

O(1)