LintCode 38 · Search a 2D Matrix II.java

	// Approach #1 - Divide-and-conquer algorithm - O(n + m) T O(1) S - just search from the corner. Every step you can easily eliminate a row and/ or col.
	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) {
	// write your code here
	if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
	return 0;
	}
	int n = matrix.length, m = matrix[0].length;
	int i = n - 1, j = 0, counter = 0;
	while (isValid(i, j, n, m)) {
	if (matrix[i][j] == target) {
	counter++;
	i--;
	j++;
	} else if (matrix[i][j] < target) {
	j++;
	} else {
	i--;
	}
	}
	return counter;
	}
	private boolean isValid(int i, int j, int n, int m) {
	return (i >= 0 && i < n && j >= 0 && j < m);
	}
	}
	// Approach #2 - O(n * log m) T O(1) S - you can binary search each row. Double the typing.
	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) {
	// write your code here
	if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
	return 0;
	}
	int counter = 0;
	for (int[] row : matrix) {
	counter += binarySearch(row, target);
	}
	return counter;
	}
	private int binarySearch(int[] row, int target) {
	int n = row.length;
	int begin = 0, end = n - 1;
	while (begin + 1 < end) {
	int mid = (end - begin) / 2 + begin;
	if (row[mid] == target) {
	return 1;
	} else if (row[mid] < target) {
	begin = mid;
	} else {
	end = mid;
	}
	}
	if (row[begin] == target) {
	return 1;
	}
	if (row[end] == target) {
	return 1;
	}
	return 0;
	}
	private boolean isValid(int i, int j, int n, int m) {
	return (i >= 0 && i < n && j >= 0 && j < m);
	}
	}

view raw LintCode 38 · Search a 2D Matrix II.java hosted with ❤ by GitHub