531 Lonely Pixel I

531. Lonely Pixel I

1. Question

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:
1
Input:
2
[['W', 'W', 'B'],
3
['W', 'B', 'W'],
4
['B', 'W', 'W']]
5
6
7
Output: 3
8
9
Explanation: All the three 'B's are black lonely pixels.
Copied!
Note:
  1. 1.
    The range of width and height of the input 2D array is [1,500].

2. Implementation

(1) DFS
1
public class Solution {
2
public int findLonelyPixel(char[][] picture) {
3
if (picture == null || picture.length == 0) {
4
return 0;
5
}
6
7
int m = picture.length, n = picture[0].length;
8
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
9
int lonelyPixel = 0;
10
11
for (int i = 0; i < m; i++) {
12
for (int j = 0; j < n; j++) {
13
if (picture[i][j] == 'B') {
14
int count = 0;
15
for (int[] direction : directions) {
16
if (!findLonelyPixelByDFS(i, j, picture, direction)) {
17
break;
18
}
19
else {
20
++count;
21
}
22
}
23
24
if (count == 4) {
25
++lonelyPixel;
26
}
27
}
28
}
29
}
30
return lonelyPixel;
31
}
32
33
public boolean findLonelyPixelByDFS(int row, int col, char[][] picture, int[] direction) {
34
row += direction[0];
35
col += direction[1];
36
37
if (row < 0 || row >= picture.length || col < 0 || col >= picture[0].length) {
38
return true;
39
}
40
41
42
if (picture[row][col] == 'B') {
43
return false;
44
}
45
46
return findLonelyPixelByDFS(row, col, picture, direction);
47
}
48
}
Copied!

3. Time & Space Complexity

DFS: 时间复杂度O(mn * Max(m, n)), m为picture的行数, n为picture的列数,分析:最坏的情况是每个pixel都是black,然后我们通过dfs从up, down, left, down四个方向检查该pixel是否lonely,这个过程需要时间O(max(m, n)), 空间复杂度: O(max(m, n))。