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

问题：

给一个长度为n-1的数组，数字的范围在 1到n(无重复)，其中有一个缺失的数字，找出该数字。要求时间复杂度为O(n)，空间复杂度为O(1).

方法1 使用公式

1 + 2 + … + n 的公式为 n*(n+1)/2，知道了总和，再前去数组的总和，即为缺失的数字。

int getMissingNo (int a[], int n){    int i, total;    total  = (n+1)*(n+2)/2;       for ( i = 0; i< n; i++)       total -= a[i];    return total;}int main(){    int a[] = {1,2,4,5,6};    int miss = getMissingNo(a,5);    printf("%d", miss);    getchar();}

 方法2 使用位运算

此方法类似 ，先对 1 到n的所有数字做异或运算，在多数组内的元素做异或运算，缺失的数字就是那个 single number。

#include
   
    int getMissingNo(int a[], int n){    int i;    int x1 = a[0];     int x2 = 1;    for (i = 1; i< n; i++)        x1 = x1^a[i];    for ( i = 2; i <= n+1; i++)        x2 = x2^i;             return (x1^x2);}int main(){    int a[] = {1, 2, 4, 5, 6};    int miss = getMissingNo(a, 5);    printf("%d", miss);    getchar();}
   

转载地址：https://blog.csdn.net/LaoJiu_/article/details/51337342 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！