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:
1
Input:
2
​
3
[['W', 'B', 'W', 'B', 'B', 'W'],    
4
 ['W', 'B', 'W', 'B', 'B', 'W'],    
5
 ['W', 'B', 'W', 'B', 'B', 'W'],    
6
 ['W', 'W', 'B', 'W', 'B', 'W']] 
7
​
8
N = 3
9
​
10
Output: 6
11
​
12
Explanation: All the bold 'B' are the black pixels we need (all 'B's at column 1 and 3).
13
        0    1    2    3    4    5         column index                                            
14
0    [['W', 'B', 'W', 'B', 'B', 'W'],    
15
1     ['W', 'B', 'W', 'B', 'B', 'W'],    
16
2     ['W', 'B', 'W', 'B', 'B', 'W'],    
17
3     ['W', 'W', 'B', 'W', 'B', 'W']]    
18
row index
19
​
20
Take 'B' at row R = 0 and column C = 1 as an example:
21
Rule 1, row R = 0 and column C = 1 both have exactly N = 3 black pixels. 
22
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.
Copied!
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
1
public class Solution {
2
    public int findBlackPixel(char[][] picture, int N) {
3
        if (picture == null || picture.length == 0) {
4
            return 0;
5
        }
6
​
7
        int m = picture.length, n = picture[0].length;
8
        int[] colCount = new int[n];
9
​
10
        // Use string at each row as key in map, so all the same row will share the same key
11
        // Map will help us to address rule 2
12
        Map<String, Integer> map = new HashMap<>();
13
​
14
​
15
        for (int i = 0; i < m; i++) {
16
            String key = getRowKey(picture, i, colCount, N);
17
            if (key.length() != 0) {
18
                map.put(key, map.getOrDefault(key, 0) + 1);
19
            }
20
        }
21
​
22
        int count = 0;
23
        for (String key : map.keySet()) {
24
            if (map.get(key) == N) {
25
                for (int j = 0; j < n; j++) {
26
                    if (key.charAt(j) == 'B' && colCount[j] == N) {
27
                        count += N;
28
                    }
29
                }
30
            }
31
        }
32
        return count;
33
    }
34
​
35
    // Convert pixels at each row to string
36
    public String getRowKey(char[][] picture, int row, int[] colCount, int N) {
37
        int rowCount = 0;
38
        StringBuilder key = new StringBuilder();
39
​
40
        for (int j = 0; j < picture[0].length; j++) {
41
            key.append(picture[row][j]);
42
            if (picture[row][j] == 'B') {
43
                ++rowCount;
44
                ++colCount[j];
45
            }
46
        }
47
        return rowCount == N ? key.toString() : "";
48
    }
49
}
Copied!
(2) 简洁版
1
class Solution {
2
    public int findBlackPixel(char[][] picture, int N) {
3
        if (picture == null || picture.length == 0) {
4
            return 0;
5
        }
6
​
7
        int m = picture.length, n = picture[0].length;
8
        int[] row = new int[m];
9
        int[] col = new int[n];
10
​
11
        Map<String, Integer> map = new HashMap();
12
​
13
        for (int i = 0; i < m; i++) {
14
            for (int j = 0; j < n; j++) {
15
                if (picture[i][j] == 'B') {
16
                    ++row[i];
17
                    ++col[j];
18
                }
19
            }
20
​
21
            if (row[i] == N) {
22
                String key = new String(picture[i]);
23
                map.put(key, map.getOrDefault(key, 0) + 1);
24
            }
25
        }
26
​
27
        int count = 0;
28
​
29
        for (String key : map.keySet()) {
30
            if (map.get(key) == N) {
31
                for (int j = 0; j < n; j++) {
32
                    if (key.charAt(j) == 'B' && col[j] == N) {
33
                        count += N;
34
                    }
35
                }
36
            }
37
        }
38
        return count;
39
    }
40
}
Copied!
3. Time & Space Complexity
Hash Table: 时间复杂度O(mn), 空间复杂度O(m + n)
531 Lonely Pixel I
542 01 Matrix
Last modified 2yr ago
Copy link
Contents
533. Lonely Pixel II
1. Question
2. Implementation
3. Time & Space Complexity
533. Lonely Pixel II​

1. Question

2. Implementation

3. Time & Space Complexity

533. Lonely Pixel II
