531. Lonely Pixel I

Description

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].

Solution

Iteration, O(m * n), S(m + n)

提前把每行和每列的'B'数量计算好，然后遍历每个'B'即可。

class Solution {
    public int findLonelyPixel(char[][] picture) {
        if (picture == null || picture.length == 0 
            || picture[0].length == 0) {
            return 0;
        }
        
        int m = picture.length;
        int n = picture[0].length;
        int[] rows = new int[m];
        int[] cols = new int[n];
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                rows[i] += picture[i][j] == 'B' ? 1 : 0;
            }
        }
        
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < m; ++i) {
                cols[j] += picture[i][j] == 'B' ? 1 : 0; 
            }
        }
        
        int count = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (picture[i][j] == 'B' && rows[i] == 1 && cols[j] == 1) {
                    ++count;
                }
            }
        }
        
        return count;
    }
}