一日一算法题，你能否识破这个简单问题的陷阱!

面试中算法题为什么那么重要？现在很多大公司都要求现场写代码，现场写代码总不能让你写个cache怎么调优，应用如何更加高效的部署吧。所以很多公司面试都会选择一些较为简单的算法题，一方面是考察你的算法基础，更重要地是看你分析问题的能力。

原题：

这个是某易游戏的一个面试题目：

• 在一个平面内，有很多很多的点，每个点都朝着一个方向运动，当两个点发生碰撞的时候，两个点会同时消失。问最后能有多少个点幸存下来？这里为了简化问题，我们假设每个点的坐标都是整数，并且运动的方向都平行于坐标轴（即上下左右） 。

我们假定n <= 100,
-1000 <= x[i] <= 1000,
-1000 <= y[i] <= 1000

思考：

这个问题，一看非常的简单，就是一些点在平面上动，然后互相碰撞就会消失。我们先来分析下什么叫做碰撞。

情况一：两个点运动后到同一个结点。

情况二：两个点相对运动

陷阱！！！特殊情况，这是这个题目最危险的地方了！这个时候蓝色的方块是不会碰撞消失的！

实现：

分析完问题，我们来看看题目的实现，大公司的面试经常是要求现场写代码的，然后要你分析时空复杂度。

这个题目有多种不同的实现方式，并且复杂度是不一样的。我们来看看几种实现方式：

1. 第一种是一秒钟一秒钟这样的模拟，为什么可以这样子做？因为横坐标纵坐标的边界都比较小两个点，极限情况下就是一个在左上方，一个在右下方，然后2000秒后瞬间爆炸。这个复杂度是（n*m）这里m指的是横纵坐标的最大距离。

2. 假如你用了第一种解法，面试官肯定会问你如果横纵坐标都非常大的时候怎么办（面试官都是这么坑的。）。解法二：我们可以每次for两遍，找出哪两个点最快碰撞（如果没有则算法结束）。然后不断更新点的坐标。特别注意思考中第3点的特殊情况。

3. 在2的基础上，我们可以采用优先队列，优先队列存的是碰撞的两点以及时间，按照碰撞时间越早的优先，可以将复杂度变为O(n*n)

干货：

这里有一个小提醒，面试中如果遇到写代码的算法题，一定要遵循kiss原则，keep it simple, stupid。这 是建立在题目已经给出数据范围的情况下，不要求更高效的算法，简单的算法也可以完美解决问题的情况下。然后解决完问题可以跟面试官主动提出你还有其他想 法。（我有一个朋友在G家面试一个开放性题目提了10种不同的见解，面试官对他印象深刻。。）当然如果这是个考察二分的题目，你非要写个枚举，那我也没办 法。。

最后欢迎大家关注我的头条号，定期推送面试相关还有码农码禽码畜感兴趣的东西。当然，如果大家有什么看不懂的，例如优先队列。。。或者想沙茶敏整理哪一方面的面试题目，可以在评论中说出来。