8 搜索m*n矩阵中目标值的个数(Search a 2D Matrix II)

目录

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 = 8n = 1008 * 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 ↩︎

上一篇:有关容斥的知识及题目解析


下一篇:组合数学