531. Lonely Pixel I

Given a picture consisting of black and white pixels, find the number of black lonely pixels.

The picture is represented by a 2D char array consisting of 'B' and 'W', which means black and white pixels respectively.

A black lonely pixel is character 'B' that located at a specific position where the same row and same column don't have any other black pixels.

Example:

Input: 
[['W', 'W', 'B'],
 ['W', 'B', 'W'],
 ['B', 'W', 'W']]

Output: 3
Explanation: All the three 'B's are black lonely pixels.

Note:

1. The range of width and height of the input 2D array is [1,500].

用兩個arrays紀錄每一個row有多少個B出現，還有每一個col有多少個B出現。最後再scan一遍，發現B時，檢查該row和該col是否都只有一個B出現，如果是的話代表這個B的row和col上只有它自己一個B。

int findLonelyPixel(vector<vector<char>>& picture) { // time: O(m * n); space: O(m + n)
    if (picture.empty() || picture[0].empty()) return 0;
    int m = picture.size(), n = picture[0].size();
    vector<int> row(m, 0), col(n, 0);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (picture[i][j] == 'B') {
                ++row[i];
                ++col[j];
            }
        }
    }
    int res = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (picture[i][j] == 'B' && row[i] == 1 && col[j] == 1) ++res;
        }
    }
    return res;
}

先找到可能的col位置，然後再scan一遍看看這些candidates的同個col上不同row是否只有一個B。

int findLonelyPixel(vector<vector<char>>& picture) { // time: O(m * n); space: O(n)
    if (picture.empty() || picture[0].empty()) return 0;
    int m = picture.size(), n = picture[0].size();
    vector<int> candidates;
    for (int i = 0; i < m; ++i) {
        int cand = -1;
        for (int j = 0; j < n; ++j) {
            if (picture[i][j] == 'B') {
                if (cand == -1) cand = j;
                else {
                    cand = -1;
                    break;
                }
            }
        }
        if (cand != -1) candidates.push_back(cand);
    }
    int res = 0;
    for (int j : candidates) {
        int B_num = 0;
        for (int i = 0; i < m; ++i) {
            if (picture[i][j] == 'B') ++B_num;
            if (B_num > 1) break;
        }
        if (B_num == 1) ++res;
    }
    return res;
}