LintCode 28. Search a 2D Matrix 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/search-a-2d-matrix/
Write an efficient algorithm that searches for a value in an m x n matrix.
This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Example
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3
, return true
.
解题思路
题意是关于查找给定的目标值target是否在一个已经排好序的m * n的二位矩阵matrix中。如果在矩阵中找到目标值,则返回true,如果不在,则返回 false。
矩阵的特点是:
- 每一排的数字由小到大排列
- 每一排第一个数字都比上一排最后一个数字大
这道题是考察Binary Search二分搜索法的应用。
- 首先,我们检查matrix是否为null或者为空。如果matrix为null或者为空,则显然找不到target,返回true。同样我们需要检查matrix中子list是否为null或者为空。因为matrix为m*n,所以只用检查第一个list即matrix[0]即可。
- 设定排数rows = matrix.length,列数为cols = matrix[0].length。
- 用一个for循环,对matrix每一排一一查找。
- 在每一排的查找中,用标准的Binary Search二分搜索法进行查找target是否在该行中。若找到,则返回true。
- 若循环结束,没有在任意一行中找到target,那么返回false。
参考代码
public class Solution { /** * @param 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 || matrix[0].length == 0 ) { return false; } int row = matrix.length; int col = matrix[0].length; // search 1st column in every row int start = 0; int end = row - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (matrix[mid][0] == target) { return true; } else if (matrix[mid][0] < target) { start = mid; } else { end = mid; } } if (matrix[start][0] == target || matrix[end][0] == target) { return true; } int possibleRow = 0; if (matrix[end][0] < target) { possibleRow = end; } else { possibleRow = start; } start = 0; end = col - 1; while (start + 1 < end) { int mid = start + (end - start) / 2; if (matrix[possibleRow][mid] == target) { return true; } else if (matrix[possibleRow][mid] < target) { start = mid; } else { end = mid; } } if (matrix[possibleRow][start] == target || matrix[possibleRow][end] == target) { return true; } return false; } }