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中缺的那个数。

1. #include <stdio.h>
   
2. 
   
3. int seekNumber(int array[],int n)
   
4. {
   
5.     int i,count;
   
6.     int number[n+1];
   
7.     for(i=0;i<=n;i++)
   
8.         number[i]=n+1;
   
9. 
   
10.     for(i=0;i<n;i++)
    
11.     {
    
12.         count=array[i];
    
13.         number[count]=0;
    
14.     }
    
15. 
    
16.     for(i=0;i<=n;i++)
    
17.     {
    
18.       if(number[i]==n+1)
    
19.           return i;
    
20.     }
    
21.     return -1;
    
22. }
    
23. 
    
24. int main()
    
25. {
    
26.     int arr[9]={1,2,5,8,0,9,6,7,4};
    
27.     int x=seekNumber(arr,9);
    
28.     printf("缺的那个数是：%d\n",x);
    
29.     return 0;
    
30. }

复制代码

wjc2118

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

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

dps521

过来看看  呵呵