目录

• 1 题目
• 2 描述
• 3 思路
  • 3.1 图解
  • 3.2 时间复杂度
  • 3.3 空间复杂度
• 4 源码

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]的模版可以很快做出。这里看一下走楼梯算法，走楼梯算法更直观，更便于记忆。走楼梯算法的步骤如下：

1. 选择左下角为起点；
2. 比较当前值和目标值；
3. 当前值>目标值，则向上走；当前值<目标值，则向右走；当前值==目标值，则向右上走，并进行计数。
4. 直到走出矩阵的边界为止。

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;
}

---

1. 搜索m*n矩阵中的目标值：https://blog.csdn.net/SeeDoubleU/article/details/118618500 ↩︎

2. 经典二分搜索：https://blog.csdn.net/SeeDoubleU/article/details/118271548 ↩︎