[leetcode]74. 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 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

这一题一看就不难，最简单暴力的方法那就是直接暴力嘛，然后只要有一个数字比他大就return false，当然这可能会超时。。

如何降低时间复杂度是一个问题。。

我看这题目的第一个想法，就是二分查找法，具体步骤比较多，要各种分类讨论，首先进行的处理，不断比较matrix[middle_row][0]和target的大小，缩小行的范围，然后同理进行列的处理就行了。。这个应该是很基本的想法。。

第二个解法是看到别人的博客的方法，这是一种剪枝的方法，写一个for循环，固定行，然后比较target和matrix[row][0]和mtarix[row][matrix[0].size() - 1]的大小，只要在两数之间就确定了在哪一行，然后直接for循环就可以确定哪一列，这个复杂度是显然是O(mn)，不过由于剪了枝，实际上用时也不长，代码如下：

bool searchMatrix(vector<vector<int>>& matrix, int target) {
	if (!matrix.size())
		return false;
	else if (!matrix[0].size())
		return false;

	for (int i = 0; i < matrix.size(); i++) {
		if (matrix[i][0] <= target) {
			if (matrix[i][matrix[0].size() - 1] >= target) {
				for (int j = 0; j < matrix[0].size(); j++) {
					if (target == matrix[i][j])
						return true;
				}
				return false;
			}
			else continue;
		}
	}
	return false;
}

后面又从剪枝的过程中想到了更简单的算法，分治。。

举个例子，假设有矩阵

  [1,   3,  5,  7]
  [10, 11, 16, 20]
  [23, 30, 34, 50]

我们要找11，这样我们可以先找一个行判断坐标judge_row = 0,列判断坐标judge_col = matrix[0].size() -1;

然后比较matrix[judge_row][judge_col] 与target，如果target比这个数字大，说明target应该在这个数字右下方，所以judge_row要向下加，列不变，反之，judge_row不变，列向左移。。

在本题中，一开始比较的是matrix[0][3] = 7 < 11。。所以我们可以把行向下移，也就是删除了第一行，

得到

  [10, 11, 16, 20]
  [23, 30, 34, 50]

然后就是20与11比，发现20> 11 所以删列得到

  
  [10, 11, 16]
  [23, 30, 34]

如此反复就OK了，一定能得到结果

代码如下：

bool searchMatrix(vector<vector<int>>& matrix, int target) {
	if (!matrix.size())
		return false;
	else if (!matrix[0].size())
		return false;

	int row = matrix.size();
	int col = matrix[0].size();

	int judge_row = 0;
	int judge_col = col - 1;
	while (judge_row < row && judge_col > 0) {
		if (target == matrix[judge_row][judge_col]) {
			return true;
		}
		else if (target > matrix[judge_row][judge_col]) {
			judge_row++;
		}
		else judge_col--;
	}
	return false;

}

这一题不难。。。但是追求效率还是要花点功夫的。。