1 題目

??搜索m*n矩陣中目標(biāo)值的個(gè)數(shù)（Search a 2D Matrix II）

lintcode：題號(hào)——38，難度——medium

2 描述

??搜索m×n矩陣中的值target，返回這個(gè)值出現(xiàn)的次數(shù)。這個(gè)矩陣具有以下特性：每行中的整數(shù)從左到右是排序的。每一列的整數(shù)從上到下是排序的。在每一行或每一列中沒有重復(fù)的整數(shù)。

??樣例1：

輸入：矩陣 = [[3,4]]，target = 3
輸出：1
解釋：

矩陣中只有1個(gè)3

??樣例2：

輸入：[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]]，target = 3
輸出：2
解釋：

矩陣中有2個(gè)3

3 思路

??該題需要對(duì)目標(biāo)值進(jìn)行計(jì)數(shù)，根據(jù)題意，目標(biāo)值出現(xiàn)的區(qū)域可能并不集中（樣例2中的兩個(gè)目標(biāo)值“3”的位置并不相鄰），需要找到一種算法能夠查找到所有目標(biāo)值。
??該題和上一題^[1]中對(duì)矩陣的約束并不相同，該題并沒有讓每一行的首位比上一行末尾大，所以上一題通過拉長(zhǎng)整個(gè)矩陣形成一個(gè)遞增序列的思路走不通。
??接下來最直觀的方式就是按行尋找，每行執(zhí)行一次二分法，判斷是否存在目標(biāo)值，統(tǒng)計(jì)找到的次數(shù)，這種方式每行耗時(shí)O(log n)，一共m行，所以時(shí)間復(fù)雜度為O(m * log n)，由于矩陣的每個(gè)橫縱都是遞增序列，執(zhí)行之前先判斷哪個(gè)維度比較大，再將較大的維度放在log真數(shù)的位置，可以有效減少耗時(shí)。

例如：m = 8，n = 100，8 * log1024 = 80要遠(yuǎn)小于1024 * log 8 = 3069。（時(shí)間復(fù)雜度的計(jì)算里log默認(rèn)以2為底數(shù)）

??再考慮上一題中最后一種思路——走樓梯算法，選擇左下角為起點(diǎn)（非要選右上角也是可以的，但左上和右下不行），將當(dāng)前位置的值和目標(biāo)值比較，大于目標(biāo)值，為了找到目標(biāo)值，則當(dāng)前位置上移一格；小于目標(biāo)值則當(dāng)前位置右移一格；等于目標(biāo)值則進(jìn)行計(jì)數(shù)，此時(shí)上一格和右一格值都不會(huì)是目標(biāo)值，所以直接向右上角斜向移動(dòng)一格。直到走出矩陣的邊界為止，查找結(jié)束，該方式耗時(shí)O(m + n)。

??按行二分法的方式時(shí)間復(fù)雜度最小，套用經(jīng)典二分搜索^[2]的模版可以很快做出。這里看一下走樓梯算法，走樓梯算法更直觀，更便于記憶。走樓梯算法的步驟如下：

1. 選擇左下角為起點(diǎn)；
2. 比較當(dāng)前值和目標(biāo)值；
3. 當(dāng)前值>目標(biāo)值，則向上走；當(dāng)前值<目標(biāo)值，則向右走；當(dāng)前值==目標(biāo)值，則向右上走，并進(jìn)行計(jì)數(shù)。
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個(gè)6

初始矩陣：

左下角5為起點(diǎn)，target目標(biāo)值為6：

當(dāng)前值5小于target，為了找到目標(biāo)值，向右走值遞增：

當(dāng)前值7大于target，向上走值遞減：

當(dāng)前值6等于target，對(duì)目標(biāo)值計(jì)數(shù)為1，并向右上走（因?yàn)橛疫叴笥?，上邊小于6，都不可能為目標(biāo)值）：

當(dāng)前值8大于target，向上走值遞減：

當(dāng)前值6等于target，對(duì)目標(biāo)值計(jì)數(shù)+1，此時(shí)為2，并向右上走：

當(dāng)前值6等于target，對(duì)目標(biāo)值計(jì)數(shù)+1，此時(shí)為3，并向右上走：

超出矩陣邊界，計(jì)數(shù)結(jié)束，查找到的目標(biāo)值計(jì)數(shù)為3個(gè)。

3.2 時(shí)間復(fù)雜度

??算法的時(shí)間復(fù)雜度為O(m + n)

3.3 空間復(fù)雜度

??算法的空間復(fù)雜度為O(1)

4 源碼

??注意事項(xiàng)：

注意橫縱邊界的值計(jì)算。

??C++版本：

/**
* @param matrix: 數(shù)值矩陣
* @param target: 目標(biāo)值
* @return: 目標(biāo)值在矩陣中出現(xiàn)的次數(shù)
*/
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;
}