leetcode531--lonely pixel I --locked

leetcode531--lonely pixel I --locked

题目

这个题目的意思是

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

意思是说要找到那些像素的个数,它出现的那一行和那一列就只能有一个它,如上面的三个‘B’,最好想的是用两个数组来分别记录每一行的这种像素点的个数, 然后再遍历一次看看它是不是这种像素点。

class Solution{
public:
    int findLonelyPixel(vector<vector<char>>& picture){
        if(picture.empty() || picture[0].empty()) return 0;
        int m = picture.size();
        int n = picture[0].size();
        int res = 0;
        
        //第一次遍历
        vector<int> rowCnt(m, 0);
        vector<int> colCnt(n,0);

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

        //第二次遍历
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(picture[i][j] == 'B'){
                    if(rowCnt[i]==1 && colCnt[j] == 1){
                        ++res;
                    }
                }
            }

        }
        return res;

    }



};


不过感觉上面的不是太好,其实第一次遍历的时候,还可以直接把是’B’的那些的坐标给存起来,这样再直接遍历这些坐标集合就可以了。相当于是申请三个数组,这样的好处是第二次不需要全部遍历一次了。

修改如下

class Solution{
public:
    int find(vector<vector<char>>& picture){
        if(picture.empyt() || picture[0].empyt()) return 0;
        int m = picture.size(), n = picture[0].size(), res = 0;
        map<int, int> pos;
        vector<int> rowCnt(m,0);
        vector<int> colCnt(n,0);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(picture[i][j]=='B'){
                    pos.insert(pair<int,int>(i,j));
                    ++rowCnt[i];
                    ++colCnt[j];
                }
            
            }
        }

        map<int,int>::iterator iter;   //迭代器.`
        for(iter=pos.begin();iter!=pos.end(); iter++){
            if(rowCnt[iter->first]==1 && colCnt[iter->second]==1){
                res++;
            }
        }
        return res;
    }


};

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦