给定平面上的n个点,问是否存在一条平行于y轴的直线,使得这n个点相对于这条直线对称。
Follow-up
是否存在一条直线使得这n个点关于这条直线对称?
算法分析
因为对称轴一定平行于y轴,这看起来缩小了穷举范围(可是我们真的要穷举可能的对称轴吗?有实无限个可能点对称轴...)
那么我们怎么找到那条对称轴?对称轴的特点就是每一个点都在另一边有一个对应的点。刷题君的第一想法是:最左边的点一定对应某个最右边的点,因此最左边的点和最右边的点的中点应该在对称轴上。当然还有很多其他的找对称轴的方法,比如求所有x坐标的平均值。
找到了对称轴的位置,我们就可以通过HashMap判断是否每一个点都有对应的点,最后输出答案即可。
时间复杂度为O(N)。
不甘寂寞的刷题君想到了一个可能的follow up:如果对称轴是任意直线呢?答案我们会在下期的微信题解里揭晓。
Read full article from Google面试题 | 轴对称_九章算法_【传送门】
No comments:
Post a Comment