[LeetCode]Line Reflection

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



我们还有一种基于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

代码如下：