L1-搜索二维矩阵

Posted on | In |

搜索二维矩阵

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

这个矩阵具有以下特性：

每行中的整数从左到右是排序的。
每行的第一个数大于上一行的最后一个整数。
样例
考虑下列矩阵：

[
[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]
]

给出 target = 3，返回 true

挑战

O(log(n) + log(m)) 时间复杂度

法一

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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[][] matrix, int target) {
	    if(matrix==null||matrix.length==0) return false;
		// write your code here
		int m = matrix.length;
		int n = matrix[0].length;
		int startIndex = 0;
		int endIndex = m * n - 1;
		boolean flag = false;
		while (startIndex<=endIndex) {
			int midIndex = (startIndex + endIndex) / 2;
			int i = midIndex / n;
			int j = midIndex % n;
			if (matrix[i][j] == target) {
				flag = true;
				break;

			} 
			else if (matrix[i][j] < target)
					startIndex = midIndex + 1;
				else
				endIndex = midIndex - 1;
			

		}
		return flag;
	
}}

法二

根据题中给出的排序状态，就可以避免无用的搜索操作啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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[][] matrix, int target) {
		// write your code here
		if (matrix == null || matrix.length == 0)
			return false;
		int m = matrix.length;
		int n = matrix[0].length;
		boolean flag = false;
		for (int i = 0; i < m && matrix[0][i] <= target; i++) {
			for (int j = 0; j < n && matrix[i][j] <= target; j++) {
				if (matrix[i][j] == target)
					flag = true;
			}

		}
		return flag;
	}
}