原题
从1到n，n个数字，每个数字只出现一次。现在，随机拿走一个数字，请给出方法，找到这个数字。
如果随机拿走两个数字呢？
如果随机拿走k个数字呢？
分析
这个题目的含义是：n-1互不相同的整数，取值范围是[1,n]，请找到1-n中，没有出现的整数(好像更难理解了:))。
当缺少一个数字的时候，很简单。计算1到n的和sum_more，然后再将n-1个整数求和，得到sum_less，则消失的数字就是(sum_more - sum_less)。
如果消失两个数字呢？按照上面的方法，假设消失的两个数字分别为a和b，1 <= a, b <= n，我们可以得到a + b = sum_more - sum_less。只有一个等式，无法确定a和b的值是多少。根据我们以前学习解方程式的经验，我们还需要一个等式，才能确定a和b的值。现在已知的条件，就只有sum_more,sum_less，这两个分别是n个数的和，以及n-2个数的和，则最终还是要在这些数字的运算形式上做文章。考虑如下两个形式：
square_sum_more = n个数的平方和 square_sum_less = n-2个数的平方和有，square_sum_more - square_sum_less = a ^ 2 + b ^ 2。又构造了一个式子。这样解如下两个式子，得到a和b，即可：
square_sum_more - square_sum_less = a ^ 2 + b ^ 2 sum_more - sum_less = a + b解比较简单了，由第二个式子得：b = sum_more - sum_less - a，带入第一个式子，则第一个式子，只有a。
如果消失三个数字呢？根据上面处理两个数字的情况，有如下的式子：
sum_more - sum_less = a + b + c square_sum_more - square_sum_less = a ^ 2 + b ^ 2 + c ^ 2 cube_sum_more - cube_sum_less = a ^ 3 + b ^ 3 + c ^ 3解出a，b，c即可。
依次类推，当消失k个数字的时候，算法的时间复杂度为O(kn)。
其他的方法：
上面的方法在n很大的情况下需要考虑溢出。。。
看看这道题“给你n个数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。”有什么感觉？
不就是缺少一个数字的情况么？当缺少一个数字的时候，相当于有n-1个数字出现了2次，1个数字出现了两次，异或一下就知道了。
再看看这道题“给你n个数，其中有且仅有两个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那两个数。”又有什么感觉？
这是缺少两个数字的情况吧。
当缺少3个数字的时候，看参考文献1吧
当缺少K个数字的时候怎么办？
就使用缺少2个数字的时候的思路吧，具体是采用分治法：知道1-n最低bit有多少个为0，多少个为1。然后统计一下，给出的数最低bit有多少个为0，多少个为1；然后就知道从最低bit为0的那部分取走了k0个数，从最低bit为1那部分取走了k1个数。 其中，k0 + k1 = k。 然后把那些数按照最低bit为0，为1分开。问题变为两个子问题k0,k1，然后再考虑次低bit。O(nlogn)
参考文章：
http://zhedahht.blog.163.com/blog/static/25411174201283084246412/