1 题目
搜索m*n矩阵中目标值的个数（Search a 2D Matrix II）
lintcode：题号——38，难度——medium
2 描述
搜索m×n矩阵中的值target，返回这个值出现的次数。这个矩阵具有以下特性：每行中的整数从左到右是排序的。每一列的整数从上到下是排序的。在每一行或每一列中没有重复的整数。
样例1：
输入：矩阵 = [[3,4]]，target = 3
输出：1
解释：矩阵中只有1个3
样例2：
输入：[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]]，target = 3
输出：2
解释：矩阵中有2个3
3 思路
该题需要对目标值进行计数，根据题意，目标值出现的区域可能并不集中（样例2中的两个目标值“3”的位置并不相邻），需要找到一种算法能够查找到所有目标值。
该题和上一题[1]中对矩阵的约束并不相同，该题并没有让每一行的首位比上一行末尾大，所以上一题通过拉长整个矩阵形成一个递增序列的思路走不通。
接下来最直观的方式就是按行寻找，每行执行一次二分法，判断是否存在目标值，统计找到的次数，这种方式每行耗时O(log n)，一共m行，所以时间复杂度为O(m * log n)，由于矩阵的每个横纵都是递增序列，执行之前先判断哪个维度比较大，再将较大的维度放在log真数的位置，可以有效减少耗时。
例如：
m = 8，n = 100，8 * log1024 = 80要远小于1024 * log 8 = 3069。（时间复杂度的计算里log默认以2为底数）
再考虑上一题中最后一种思路——走楼梯算法，选择左下角为起点（非要选右上角也是可以的，但左上和右下不行），将当前位置的值和目标值比较，大于目标值，为了找到目标值，则当前位置上移一格；小于目标值则当前位置右移一格；等于目标值则进行计数，此时上一格和右一格值都不会是目标值，所以直接向右上角斜向移动一格。直到走出矩阵的边界为止，查找结束，该方式耗时O(m + n)。
按行二分法的方式时间复杂度最小，套用经典二分搜索[2]的模版可以很快做出。这里看一下走楼梯算法，走楼梯算法更直观，更便于记忆。走楼梯算法的步骤如下：
- 选择左下角为起点；
- 比较当前值和目标值；
- 当前值>目标值，则向上走；当前值<目标值，则向右走；当前值==目标值，则向右上走，并进行计数。
- 直到走出矩阵的边界为止。
3.1 图解
输入：[
[1, 2, 3, 6, 8],
[2, 4, 6, 9, 10],
[3, 5, 8, 10, 14]]，
[4, 6, 9, 12, 17]]，
[5, 7, 10, 14, 18]]，target = 6
输出：3
解释：矩阵中有3个6
初始矩阵：
\[\begin{bmatrix} 1&2&3&6&8\\ 2&4&6&9&10\\ 3&5&8&10&14\\ 4&6&9&12&17\\ 5&7&10&14&18\\ \end{bmatrix} \]左下角5为起点，target目标值为6：
\[\begin{bmatrix} 5\\ \end{bmatrix} \]当前值5小于target，为了找到目标值，向右走值递增：
\[\begin{bmatrix} 5&7\\ \end{bmatrix} \]当前值7大于target，向上走值递减：
\[\begin{bmatrix} &6\\ 5&7\\ \end{bmatrix} \]当前值6等于target，对目标值计数为1，并向右上走（因为右边大于6，上边小于6，都不可能为目标值）：
\[\begin{bmatrix} &&8\\ &6\\ 5&7\\ \end{bmatrix} \]当前值8大于target，向上走值递减：
\[\begin{bmatrix} &&6\\ &&8\\ &6\\ 5&7\\ \end{bmatrix} \]当前值6等于target，对目标值计数+1，此时为2，并向右上走：
\[\begin{bmatrix} &&&6\\ &&6\\ &&8\\ &6\\ 5&7\\ \end{bmatrix} \]当前值6等于target，对目标值计数+1，此时为3，并向右上走：
\[\begin{bmatrix} 1&2&3&(6)&8\\ 2&4&(6)&9&10\\ 3&5&(8)&10&14\\ 4&(6)&9&12&17\\ (5)&(7)&10&14&18\\ \end{bmatrix} \]超出矩阵边界，计数结束，查找到的目标值计数为3个。
3.2 时间复杂度
算法的时间复杂度为O(m + n)
3.3 空间复杂度
算法的空间复杂度为O(1)
4 源码
注意事项：
注意横纵边界的值计算。
C++版本：
/**
* @param matrix: 数值矩阵
* @param target: 目标值
* @return: 目标值在矩阵中出现的次数
*/
int searchMatrix(vector<vector<int>> &matrix, int target) {
// write your code here
if (matrix.empty() || matrix.front().empty())
{
return 0;
}
int row = matrix.size() - 1;
int col = 0;
int count = 0;
while (row >= 0 && col <= matrix.front().size() - 1)
{
if (matrix.at(row).at(col) > target)
{
row--;
}
else if (matrix.at(row).at(col) < target)
{
col++;
}
else
{
row--;
col++;
count++;
}
}
return count;
}