今天闲来无事看到一个算法题，觉得很好，遂学习一下
题目是这样的：
一个无序数组里有99个不重复正整数，范围从1到100，唯独缺少一个整数。如何找出这个缺失的整数？
解法一：
创建一个HashMap，以1到100为键，值都是0 。然后遍历整个数组，每读到一个整数，就找到HashMap当中对应的键，让其值加一。由于数组中缺少一个整数，最终一定有99个键对应的值等于1, 剩下一个键对应的值等于0。遍历修改后的HashMap，找到这个值为0的键。假设数组长度是N，那么该解法的时间复杂度是O（1），空间复杂度是O（N）。
解法一在时间上是最优的，但是开辟了额外的空间，那么怎么样才能降低空间复杂度呢？
解法二：
先把数组元素进行排序，然后遍历数组，检查任意两个相邻元素数值是否是连续的。如果不连续，则中间缺少的整数就是所要寻找的；如果全都连续，则缺少的整数不是1就是100。假设数组长度是N，如果用时间复杂度为O（N*LogN）的排序算法进行排序，那么该解法的时间复杂度是O（N*LogN），空间复杂度是O（1）。
解法二中，在空间上是最优的，但是时间复杂度又增大了，怎么样才能使空间复杂度和时间复杂度都最优呢？
解法三：
很简单也很高效的方法，先算出1+2+3....+100的合，然后依次减去数组里的元素，最后得到的差，就是唯一缺失的整数。假设数组长度是N，那么该解法的时间复杂度是O（N），空间复杂度是O（1）。
这是一到很简单的算法题，但是可以从中学到很多，有些问题看上去很难，但是换个思路想问题，问题就会变得简单又高效，在工作中，如果我们觉得遇到了复杂的问题，不妨换一个思路想想，没准就能想到一个既简单又高效的解决方法。这道题目使我想起了我之前的一次面试的笔试题目，上边第一题是这样的一个题目：
两辆火车在同一轨道中对向行驶，距离300km，速度都是75km/h，在两火车中间有一只苍蝇在火车头A到火车头B之间来回飞，速度为30km/h，问：在这两辆火车相撞时，苍蝇一共飞的距离是多少？
当我看到这个题目的时候，我先告诉自己是参加的JAVA工程师的面试，而不是初高中的数学考试，首先排除掉了一般脑回路第一时间想起来的那种解法，就是一点一点加苍蝇飞的距离，然后脑子飞快运转想距离=时间X速度，速度题目上有了，时间呢？时间不就是两辆火车相撞嘛，嗨呀！这不就是300/（75+75)X30=60km。问题迎刃而解，在那次笔试中，有好几道这种题目，都是乍看一下很复杂，但是只要换个思路想，问题就会变得很简单，甚至都想笑。
学无止境，我心中一直告诉自己：这个问题可能还有更简单的方法，我想，这就是我喜欢编程的原因，在摸索中寻找更高效的方法，这就是编程之美。
同时欢迎关注我的微信公众号：猿人族永不为奴。
二维码：