0到n个自然数乱序排放在数组中……

wjc2118

0到n个自然数乱序排放在数组中，中间缺少了一个数，要求把缺少的数找出来，都有哪些方法，复杂度是多少？？

有一种解法是：在内存中创建一个同样大的数组，把乱序的数组按顺序存放进新数组，再折半查找，复杂度为n+logn
请问还有什么方法啊？？？

愣头小兵

不能用排序，排序的时间复杂度最少也是nlogn。我给你个方法，时间复杂度是n。
array[]中存了0至N的乱序自然数，总元素n个，中间 缺少一个数，seekNumber(int array[],int n)函数返回缺的那个数。算法实现：建一个有n+1个元素的数组number,全部初始化值为n+1；遍历数组array,以数组array中的每个元素值为number数组的下标，将这些number数组中元素的值赋值为零。然后遍历数组number,如果number中某个元素的值仍然还为n+1，那么这个元素的下标一定是原来array中缺的那个数。

#include <stdio.h>

int seekNumber(int array[],int n)
{
    int i,count;
    int number[n+1];
    for(i=0;i<=n;i++)
        number[i]=n+1;

    for(i=0;i<n;i++)
    {
        count=array[i];
        number[count]=0;
    }

    for(i=0;i<=n;i++)
    {
      if(number[i]==n+1)
          return i;
    }
    return -1;
}

int main()
{
    int arr[9]={1,2,5,8,0,9,6,7,4};
    int x=seekNumber(arr,9);
    printf("缺的那个数是：%d\n",x);
    return 0;
}

wjc2118

愣头小兵 发表于 2015-11-25 20:56
不能用排序，排序的时间复杂度最少也是nlogn。我给你个方法，时间复杂度是n。
array[]中存了0至N的乱序自 ...

厉害！！请问你是怎么想到的呗？？我总是看过答案才觉得豁然开朗，就是不知道怎么才能想出这个答案。。。

dps521

过来看看  呵呵