九章演算法 | Google面試題：軸對稱
01-31
撰文 | JZ
專欄 | 九章演算法
題目描述
給定平面上的n個點，問是否存在一條平行於y軸的直線，使得這n個點相對於這條直線對稱。
Follow-up
是否存在一條直線使得這n個點關於這條直線對稱？
演算法分析
因為對稱軸一定平行於y軸，這看起來縮小了窮舉範圍（可是我們真的要窮舉可能的對稱軸嗎？有實無限個可能點對稱軸...）
那麼我們怎麼找到那條對稱軸？對稱軸的特點就是每一個點都在另一邊有一個對應的點。刷題君的第一想法是：最左邊的點一定對應某個最右邊的點，因此最左邊的點和最右邊的點的中點應該在對稱軸上。當然還有很多其他的找對稱軸的方法，比如求所有x坐標的平均值。
找到了對稱軸的位置，我們就可以通過HashMap判斷是否每一個點都有對應的點，最後輸出答案即可。
時間複雜度為O(N)。
不甘寂寞的刷題君想到了一個可能的follow up：如果對稱軸是任意直線呢？答案我們會在下期的微信題解里揭曉。
參考程序
面試官角度分析
這是一道簡單難度的題，兼具演算法設計（找對稱軸）和數據結構（考察hashmap），雖然簡單但是可以區分一部分面試者。對於想要 達到hire的同學是必須在面試時AC的。
LintCode相關練習題
Max points on a line
推薦閱讀：