[TOC]

1. 孤独像素 I

https://leetcode-cn.com/problems/lonely-pixel-i/

1.1. 输入

给你一个大小为 m * n 的图像 picture ，图像由黑白像素组成，'B' 表示黑色像素，'W' 表示白色像素，

黑色孤独像素 的定义为：

如果黑色像素 'B' 所在的同一行和同一列不存在其他黑色像素，那么这个黑色像素就是黑色孤独像素。

1.2. 输出

• 请你统计并返回图像中 黑色 孤独像素的数量。

1.3. 示例

1.3.1. 示例1

picture = [
          ["W","W","B"],
          ["W","B","W"],
          ["B","W","W"]
          ]
输入：picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
输出：3
解释：全部三个 'B' 都是黑色的孤独像素

1.3.2. 示例2

picture = [
            ["B","B","B"],
            ["B","B","W"],
            ["B","B","B"]
        ]
输入：picture = [["B","B","B"],["B","B","W"],["B","B","B"]]
输出：0

1.4. 方法

1.4.1. 方法1 暴力法

思路

步骤：

1. 遍历每一个黑色像素。

2. 再根据当前像素行列，判断是否行和列都仅有一个黑色像素。是则黑色孤独像素，否则非。

判断条件：

• 如果有白色像素，必然不是黑色孤独像素，故当前像素是黑色像素才可进行黑色孤独像素判断。
• 当且仅当 当前黑色像素的行列都只有一个黑色像素时，此时是一个黑色孤独像素。

代码

class Solution {
public:
    //暴力法 时间复杂度O(raw*col*(raw+col))
    static int findLonelyPixel(std::vector<std::vector<char>>& picture) {
        int raws = picture.size();
        int cols = picture[0].size();
        int counts = 0;
        for (size_t i = 0; i < raws; i++)//raw
        {
            for (size_t j = 0; j < cols; j++) {//col

                if (picture[i][j] == 'B') {
                    int isBlackRaw = 0;
                    int isBlackCol = 0;
                    for (size_t k = 0; k < raws; k++)
                    {
                        if (picture[i][k] == 'B') {
                            isBlackRaw++;
                        }
                    }

                    for (size_t k = 0; k < cols; k++)
                    {
                        if (picture[k][j] == 'B') {
                            isBlackCol++;
                        }
                    }

                    if (isBlackCol == 1 && isBlackRaw == 1) {
                        counts++;
                    }
                }
            }
        }

        return counts;
    }
};

1.4.2. 方法2 预处理法

思路

在暴力遍历时，会有步骤1遍历一次黑色像素，步骤2 循环内又遍历了一次黑色像素。就是n*n次循环了。

所以改良方法就是在步骤1的遍历一遍，把每个行、列的黑色像素数量保存一份，在出循环，再遍历一次。

步骤：

1. 遍历黑色像素，记录行、列的黑色像素数量。
2. 再遍历一次，当前像素为 黑色像素 且 其行数组和列数组的黑色像素数量为1。

判断条件：

• 当前像素为 黑色像素 且 其行黑色像素数量和列黑色像素数量的数量为1。

代码

class Solution {
public:
    //预处理法 O(raw*col)
    static int findLonelyPixel(std::vector<std::vector<char>>& picture) {
        int counts = 0;
        int raws = picture.size();
        int cols = picture[0].size();
        int max = raws > cols?raws:cols;
        std::vector<char> rawValue(max, 0);
        std::vector<char> colValue(max, 0);

        for (size_t i = 0; i < raws; i++)//raw
        {
            for (size_t j = 0; j < cols; j++) {//col
                if (picture[i][j] == 'B') {
                    rawValue[i]++;
                    colValue[j]++;
                }
            }
        }

        for (size_t i = 0; i < raws; i++)//raw
        {
            for (size_t j = 0; j < cols; j++) {//col

                if(picture[i][j] == 'B'){
                    if (rawValue[i] == 1 && colValue[j] == 1) {
                        counts++;
                    }
                }
            }
        }

        return counts;
    }
};