首页 > 数学相关 > 寻找缺失的数字
2014
07-14

寻找缺失的数字

Question

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.

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

Example:
I/P    [1, 2, 4, ,6, 3, 7, 8]
O/P    5

 方法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 使用位运算

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

#include<stdio.h>

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();
}

方法1会出现计算溢出的问题,方法2则没有此问题。

参考:http://www.geeksforgeeks.org/find-the-missing-number/


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.