这是我面试A公司时碰到的算法题，题目大意是一本书缺了一页，然后书页顺序被打乱，问如何迅速找到缺失的那一页？
思路：其实就是在乱序数组里面找缺失的一个数，有以下方法
1、直接排序，然后遍历一次 时间复杂度O(NlogN),不需要额外空间
2、用bitmap思想，开一个大数组，可以用bitset以节省空间，遍历一遍该数组，出现的数字置位为1，遍历完毕后，没有置位的那一位对应的数就是缺失的数字，时间复杂度O(N),但是需要O（N）的额外空间
3、原地桶排序思想，遍历数组，如果脚标与值相等不做任何处理；否则交换该数到其值索引的那个位置，对于被占用位置的数字，采用同样的方法放到其值索引的位置，直到数组末尾，此时只有空缺的那个数为脚标的那个数的值不等于其脚标。复杂度O（N），且没有额外空间，是最佳算法
算法实现如下，以10个数字为例
#include <iostream>
using namespace std;
int main(){
int a[10] = {3,2,4,9,6,1,0,8,7,-1};
int temp;
int temp_val;
for(int i = 0; i < 10; i++){
if(a[i] != i){
temp_val = temp = a[a[i]];//临时变量先存储需要更换的值
a[a[i]] = a[i];
a[i] = temp;
}
while(a[temp_val] != temp_val){
temp = a[temp_val];
a[temp_val] = temp_val;
temp_val = temp;
if(temp_val == -1) break;
}
}
for(int j = 0; j < 10; j++){
cout<<a[j]<<endl;
if(a[j] != j) cout<<"the miss number is"<<j<<endl;
}
return 0;
}