[LeetCode]Lonely Pixel II

和Lonely Pixel I的区别是，我们不能用第一行和第一列来记录了，因为N可能很大，而我们只有256个ASCII字记录是远远不够的。根据题目的要求我们开一个数组记录每一列的B数目，因为要求有B的行是一样的，所以我们需要一个map，来记录所有B数目为N的行数相同的数量。之后遍历map，确立其有N个一样的行，并且对应的col有N个B，那么这几个行和列相交的B都是答案，以此类推求出所有B。时间复杂度O(m * n)，空间复杂度O(m * n)，代码如下：

	class Solution {
	public:
	int findBlackPixel(vector<vector<char>>& picture, int N) {
	int m = picture.size(), n = m? picture[0].size(): 0;
	vector<int> cols(n, 0);
	map<string, int> map;
	for(int i = 0; i < m; ++i)
	{
	string key = "";
	int count = 0;
	for(int j = 0; j < n; ++j)
	{
	key += picture[i][j];
	if(picture[i][j] == 'B')
	{
	++count;
	++cols[j];
	}
	}
	if(count == N)
	++map[key];
	}
	int res = 0;
	for(auto& p : map)
	{
	for(int i = 0; i < n; ++i)
	{
	if(p.first[i] == 'B' && cols[i] == N && p.second == N)
	res += N;
	}
	}
	return res;
	}
	};

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