[LeetCode]Lonely Pixel I

 用额外空间的话很简单，我们只需要开row和column两个数组来记录每个row和column B的数量，之后在扫一遍找lonely pixel。但是我们还有in place的做法，我们可以把第一行和第一列每一个数特殊处理来统计当前行或者列的B数量，注意[0][0]的数只可能统计0行或者0列，所以我们还需要额外一个变量来帮助统计剩下一行或者列的情况。另外一点就是注意区分原第一行/列的数是否本来就是B，为了区分这个我们用不同的标记。常数空间，时间复杂度O(m * n)，代码如下：

	class Solution {
	public:
	int findLonelyPixel(vector<vector<char>>& picture) {
	int m = picture.size(), n = m? picture[0].size(): 0, firstRowCount = 0;
	for(int i = 0; i < m; ++i)
	{
	for(int j = 0; j < n; ++j)
	{
	if(picture[i][j] == 'B')
	{
	//we are using first row and column to count black pixels in each row/col
	//but we also need to mark if original place contains black pixel
	//columns
	if((picture[0][j] == 'W' || picture[0][j] == 'B' || picture[0][j] == 'X') && i)
	++picture[0][j];
	//rows
	if(!i)
	++firstRowCount;
	else
	{
	if((picture[i][0] == 'W' || picture[i][0] == 'B' || picture[i][0] == 'X') && j)
	++picture[i][0];
	}
	}
	}
	}
	int count = 0;
	for(int i = 0; i < m; ++i)
	{
	for(int j = 0; j < n; ++j)
	{
	if(picture[i][j] == 'B')
	{
	bool colValid = picture[0][j] == 'B' || picture[0][j] == 'X';
	bool rowValid = i? picture[i][0] == 'B' || picture[i][0] == 'X': firstRowCount == 1;
	if(colValid && rowValid)
	++count;
	}
	}
	}
	return count;
	}
	};

view raw Lonely Pixel I.cpp hosted with ❤ by GitHub