本文共 670 字，大约阅读时间需要 2 分钟。

有一组数字，从1到n，中减少了一个数，顺序也被打乱，放在一个n-1的数组里

请找出丢失的数字，最好能有程序，最好算法比较快

#include <cstdlib>#include <iostream>using namespace std;int findMissNum(int *a, int count){ int res = 0; for(int i=0; i< count; i++) res ^= a[i] ^ (i + 1); res ^= count + 1; return res;}int main(int argc, char *argv[]){ int a[] = {1, 2, 3, 4, 5, 6, 8, 9, 10}; cout << findMissNum(a, sizeof(a) / sizeof(int)) << endl; system("PAUSE"); return EXIT_SUCCESS;} 

由于数组中的元素都是1~n之间的数， 把数组中的每个元素与他的序号做异或， 然后把这些所有的结果在做异或， 最终的结果就是缺失的那个数， 1 ^1 ^2^2 ^3 = 3;

如果对空间没有要求， 就是用bitmap， 申请个n个元素的位数组ass[n + 1]， 然后遍历原数组a[]， 将相应的ass[a[i]]置为1， 等遍历完后， 看看ass[]数组中那个元素还没有被赋值， 就是缺失的那个数字了... 

转载地址：http://ojkqb.baihongyu.com/