533 Lonely Pixel II

533. Lonely Pixel II

1. Question

Given a picture consisting of black and white pixels, and a positive integer N, find the number of black pixels located at some specific row R and column C that align with all the following rules:

1. Row R and column C both contain exactly N black pixels.

2. For all rows that have a black pixel at column C, they should be exactly the same as row R

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

Example:

Input:

[['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'W', 'B', 'W', 'B', 'W']] 

N = 3

Output: 6

Explanation: All the bold 'B' are the black pixels we need (all 'B's at column 1 and 3).
        0    1    2    3    4    5         column index                                            
0    [['W', 'B', 'W', 'B', 'B', 'W'],    
1     ['W', 'B', 'W', 'B', 'B', 'W'],    
2     ['W', 'B', 'W', 'B', 'B', 'W'],    
3     ['W', 'W', 'B', 'W', 'B', 'W']]    
row index

Take 'B' at row R = 0 and column C = 1 as an example:
Rule 1, row R = 0 and column C = 1 both have exactly N = 3 black pixels. 
Rule 2, the rows have black pixel at column C = 1 are row 0, row 1 and row 2. They are exactly the same as row R = 0.

Note:

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

2. Implementation

(1) Hash Table

思路: 这道题让我们找到有多少个黑色pixel它们所处的位置满足以下两个条件:

1.黑色pixel所在的行和列的黑色pixel个数都是N，这个和lonely pixel 1类似

2.在第i列包含黑色pixel的所有行中，它们都必须是一样的。这里的一样指的是行里的pixel的排列是一样的。

因为第二个条件的存在,所以我们必须用一个方法表示行的排列，这里可以利用每行的pixel排列作为key，然后放在一个hashmap里。当我们将所有行的排列都转成string的key放在hashmap后， 再遍历这个map，由于题目的要求, 只有当map.get(key) 等于 N时，我们才继续查看每列中的黑色pixel的个数是否为N以及当前列的pixel是否为黑色pixel，如果是的话 count 加N. 由于我们只关心黑色pixel个数为N的行，所以在getRowKey(), 如果当前行的黑色pixel个数不为N，我们直接返回empty string

public class Solution {
    public int findBlackPixel(char[][] picture, int N) {
        if (picture == null || picture.length == 0) {
            return 0;
        }

        int m = picture.length, n = picture[0].length;
        int[] colCount = new int[n];

        // Use string at each row as key in map, so all the same row will share the same key
        // Map will help us to address rule 2
        Map<String, Integer> map = new HashMap<>();


        for (int i = 0; i < m; i++) {
            String key = getRowKey(picture, i, colCount, N);
            if (key.length() != 0) {
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
        }

        int count = 0;
        for (String key : map.keySet()) {
            if (map.get(key) == N) {
                for (int j = 0; j < n; j++) {
                    if (key.charAt(j) == 'B' && colCount[j] == N) {
                        count += N;
                    }
                }
            }
        }
        return count;
    }

    // Convert pixels at each row to string
    public String getRowKey(char[][] picture, int row, int[] colCount, int N) {
        int rowCount = 0;
        StringBuilder key = new StringBuilder();

        for (int j = 0; j < picture[0].length; j++) {
            key.append(picture[row][j]);
            if (picture[row][j] == 'B') {
                ++rowCount;
                ++colCount[j];
            }
        }
        return rowCount == N ? key.toString() : "";
    }
}

(2) 简洁版

class Solution {
    public int findBlackPixel(char[][] picture, int N) {
        if (picture == null || picture.length == 0) {
            return 0;
        }

        int m = picture.length, n = picture[0].length;
        int[] row = new int[m];
        int[] col = new int[n];

        Map<String, Integer> map = new HashMap();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (picture[i][j] == 'B') {
                    ++row[i];
                    ++col[j];
                }
            }

            if (row[i] == N) {
                String key = new String(picture[i]);
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
        }

        int count = 0;

        for (String key : map.keySet()) {
            if (map.get(key) == N) {
                for (int j = 0; j < n; j++) {
                    if (key.charAt(j) == 'B' && col[j] == N) {
                        count += N;
                    }
                }
            }
        }
        return count;
    }
}

3. Time & Space Complexity

Hash Table: 时间复杂度O(mn), 空间复杂度O(m + n)