[LeetCode]Image Overlap

假设输入数组的维度为n，Brute Force的做法是对于每一个在A中的点遍历每一个移动的可能，比如第一个点可以平移到B中的(0,0), (0,1)...以此类推。总共有n^2 * n ^2 = n^4种可能，之后我们还要花n^2的时间统计有多少覆盖的点，所以时间复杂度为O(n^6)。一个优化是，我们只需要枚举A中和B中的所有点，计算每一对的距离，然后用map统计距离相同的点有多少个，取最多的即可。时间复杂度为O(n^4)。代码如下：

	class Solution {
	public:
	int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
	int n = A.size();
	vector<int> pointsA, pointsB;
	for (int i = 0; i < n; ++i)
	{
	for (int j = 0; j < n; ++j)
	{
	if (A[i][j])pointsA.push_back(i * n + j);
	if (B[i][j])pointsB.push_back(i * n + j);
	}
	}
	unordered_map<string, int> dist;
	int res = 0;
	for (const auto& pA : pointsA)
	{
	for (const auto& pB : pointsB)
	{
	int xA = pA / n, yA = pA % n, xB = pB / n, yB = pB % n;
	string key = to_string(xA - xB) + ":" + to_string(yA - yB);
	++dist[key];
	res = max(res, dist[key]);
	}
	}
	return res;
	}
	};

view raw Image Overlap.cpp hosted with ❤ by GitHub