Google面试题 | 轴对称_九章算法_【传送门】



Google面试题 | 轴对称_九章算法_【传送门】

给定平面上的n个点,问是否存在一条平行于y轴的直线,使得这n个点相对于这条直线对称。

Follow-up 

是否存在一条直线使得这n个点关于这条直线对称?


算法分析 

因为对称轴一定平行于y轴,这看起来缩小了穷举范围(可是我们真的要穷举可能的对称轴吗?有实无限个可能点对称轴...)


那么我们怎么找到那条对称轴?对称轴的特点就是每一个点都在另一边有一个对应的点。刷题君的第一想法是:最左边的点一定对应某个最右边的点,因此最左边的点和最右边的点的中点应该在对称轴上。当然还有很多其他的找对称轴的方法,比如求所有x坐标的平均值。


找到了对称轴的位置,我们就可以通过HashMap判断是否每一个点都有对应的点,最后输出答案即可。


时间复杂度为O(N)


不甘寂寞的刷题君想到了一个可能的follow up:如果对称轴是任意直线呢?答案我们会在下期的微信题解里揭晓。


Read full article from Google面试题 | 轴对称_九章算法_【传送门】


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts