[LeetCode]Line Reflection

如果所有点都能找到对称点的话，我们只需要找到最大最小值，就能确定对应的对称y轴所在的位置。然后对于每一个点，在知道了对称轴之后，去寻找对称的点时候存在即可。时间复杂度O(n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	bool isReflected(vector<pair<int, int>>& points) {
	int len = points.size(), maxVal = INT_MIN, minVal = INT_MAX;
	unordered_map<long, unordered_set<int>> map;
	for(auto&& p : points)
	{
	map[p.first].insert(p.second);
	maxVal = max(maxVal, p.first);
	minVal = min(minVal, p.first);
	}
	long sum = minVal + maxVal;
	for(auto&& p : points)
	{
	if(map[sum - p.first].find(p.second) == map[sum - p.first].end())
	return false;
	}
	return true;
	}
	};

view raw Line Reflection_1.cpp hosted with ❤ by GitHub

我们还有一种基于sorting的O(n * log n)时间，O(1)空间的解法。同样先找到对称轴，然后从头尾向中间check首尾两个点left和right是不是对称即可。这里有几个点要注意的是：

1. 我们用int存对称轴，但是对称轴真正在的位置可能是用double表示。但是这并没有关系，因为我们每次check对称的时候是check当前left和right和左右边界的差值是否一样。对于x正好和对称轴的int part重合的情况，如果其正好就是对称轴，那么x和左右边界的差值一定也一样，否则就不一样。
2. 对于x轴值相同y轴值不相同的数，为了保证首尾check时能check到对应的点。对应x小于对称轴的点， 按y值从小到大tie break。x大对称轴的点，按y值从大到小tie break。比如，[-1, 1], [-1, 2], [0, 0], [1, 1], [1, 2] sort之后就会变为[-1, 1], [-1, 2], [0, 0], [1, 2], [1, 1]
3. 对于x和对称轴相等的点，我们不必担心。因为我们每次会先check1的情况，如果满足1.则所有x轴值等于对称轴的点都在对称轴上。也就是说，如果left和right都碰到对称轴，return true。
4. 这个题目允许多个点对称一个点，比如[1, 16], [1, 16], [-1, 16]的情况，我们也return true。那么对于重合的点，我们需要跳过。
5. 如果我们两个点x轴满足条件，但是y轴不相等，return false

代码如下：

	class Solution {
	public:
	bool isReflected(vector<pair<int, int>>& points) {
	int len = points.size(),maxVal = INT_MIN, minVal = INT_MAX, left = 0, right = len - 1;
	for(auto&& p : points)
	{
	maxVal = max(maxVal, p.first);
	minVal = min(minVal, p.first);
	}
	int mid = minVal + (maxVal - minVal) / 2;
	auto comp = [&mid](const pair<int, int>& p1, const pair<int, int>& p2){return p1.first == p2.first? (p1.first <= mid? p1.second < p2.second: p1.second > p2.second): p1.first < p2.first;};
	sort(points.begin(), points.end(), comp);
	while(left <= right)
	{
	//[16,1], [16, 1], [16, -1]
	while(left > 0 && points[left] == points[left - 1])++left;
	while(right < len - 1 && points[right] == points[right + 1])--right;
	if(left > right)break;
	auto pL = points[left], pR = points[right];
	if(pL.first - minVal != maxVal - pR.first)return false;
	if(pL.first == pR.first)return true;
	if(pL.second != pR.second)return false;
	++left;
	--right;
	}
	return true;
	}
	};

view raw Line Reflection_2.cpp hosted with ❤ by GitHub