0531._Lonely_Pixel_I.md

531. Lonely Pixel I

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/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:
The range of width and height of the input 2D array is [1,500].

解题方案

思路 1 - 时间复杂度: O(row * col)- 空间复杂度: O(row)******

无脑，先求出可能的row以及其Black所在的坐标，再从这些candidates里面挑选col也符合的，最后返回数量即可

beats 95.38%

class Solution(object):
    def findLonelyPixel(self, picture):
        """
        :type picture: List[List[str]]
        :rtype: int
        """
        row = len(picture)
        col = len(picture[0]) if row else 0
        
        candi_coors = []
        for i in range(row):
            count_B = 0
            col_idx_B = sys.maxsize
            for j in range(col):
                if picture[i][j] == 'B':
                    count_B += 1
                    col_idx_B = j
                    if count_B > 1:
                        break
            if count_B == 1:
                candi_coors.append((i,col_idx_B))
                
        candi_cols = set([j for i, j in candi_coors])
        real_cols_lookup = {}
        
        for col_idx in candi_cols:
            count_B = 0
            for i in range(row):
                if picture[i][col_idx] == 'B':
                    count_B += 1
                    if count_B > 1:
                        break
            if count_B == 1:
                real_cols_lookup[col_idx] = 1
                
        res = 0
        for row_idx, col_idx in candi_coors:
            if col_idx in real_cols_lookup:
                res += 1
        return res