【题目描述】
Giving a string with number from 1-n in random order, but miss 1 number.Find that number.
Notice: n <= 30
Example
Given n = 20, str = 19201234567891011121314151618
return 17
给一个由 1 - n 的整数随机组成的一个字符串序列，其中丢失了一个整数，请找到它。
注意：n <= 30
样例
给出 n = 20, str = 19201234567891011121314151618
丢失的数是 17 ，返回这个数。
【题目链接】
www.lintcode.com/en/problem/find-the-missing-number-ii/
【题目解析】
相对好的方法是取中间或者取随机数。
最直接简单的办法，以空间换时间，加一个bool数组再哈希就可以了。
最优雅的法子横空出世 — 异或。两个相同的数异或为0。故而把原数组与0-n异或和就为最后的结果。
借助桶排序。思路是：从0开始遍历到n-1，每次当a[i]!=i的时候，将a[i]与a[a[i]]交换，大于边界的话，就丢掉，直到无法交换位置。那个特殊值有两种情况，一种是在0~n-1之间，那么经过a[i]与a[a[i]]交换，最后以特殊值为下标的位置上一定为n；另一种是特殊值为n，那么a[i]与a[a[i]]交换对于0~n-1都满足。故而只要跟踪边界值n即可，跟踪值x应初始化为n，以对应第二种情况。
【参考答案】
