0到n个自然数乱序排放在数组中……
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;
for(i=0;i<=n;i++)
number=n+1;
for(i=0;i<n;i++)
{
count=array;
number=0;
}
for(i=0;i<=n;i++)
{
if(number==n+1)
return i;
}
return -1;
}
int main()
{
int arr={1,2,5,8,0,9,6,7,4};
int x=seekNumber(arr,9);
printf("缺的那个数是：%d\n",x);
return 0;
}
愣头小兵 发表于 2015-11-25 20:56
不能用排序，排序的时间复杂度最少也是nlogn。我给你个方法，时间复杂度是n。
array[]中存了0至N的乱序自 ...
厉害！！请问你是怎么想到的呗？？我总是看过答案才觉得豁然开朗，就是不知道怎么才能想出这个答案。。。 过来看看呵呵
页:
[1]