再发一道百度笔试题(搜索新产品研发部试题)
简述:n个空间,存放a到a+n-1的数,位置随机且数字不重,a为正且未知.
现在第一个空间的数被误设置为-1.

说明:已经知道被修改的数不是最小的.

例子:n=6, a=2,原始的串为5, 3, 7, 6, 2, 4.现在被别人修改为-1, 3, 7, 6, 2, 4.
现在希望找到5.

限制:n不超过1M,现在希望找出这个数,并且实现尽量快.

要求:完成函数(实现尽可能高效)
unsigned int find_lost(const int* source, const length)
source为数组起址,length为长度.

给出思路(文字描述),完成代码,并且分析你算法的时间复杂度.

[解决办法]
////quicksort
extern int Partition(int *,int,int);
void QuickSort(int * arry,int p,int r)
{
int q;
if(p<r)
{
q=Partition(arry,p,r);
QuickSort(arry,p,q-1);
QuickSort(arry,q+1,r);
}
}

int Partition(int * arry,int p,int r)
{
int i,j,temp;
i=p;
for(j=p+1;j<=r;j++)
{
if(arry[j]<=arry[p])
{
i++;
temp=arry[i];
arry[i]=arry[j];
arry[j]=temp;
}
}
temp=arry[i];
arry[i]=arry[p];
arry[p]=temp;
return i;
}
/////////////////////////////////////////////////////
int main(void)
{
int arry[6]={-1,3,7,6,2,4};
QuickSort(arry,0,5);
for(int i=1;i<6;i++)
{
if(arry[i]!=arry[i+1]-1)
{
break;
}
}
cout<<"the number is"<<ends;
cout<<arry[i]+1<<endl;
return 0;
}
//////////////////////////////
补充：可以采用线性时间的排序算法，这样就可以使这个算法达到0(n)的时间复杂度
[解决办法]
思路：
此题关键是hash函数H(X)的设计，为了减少数组遍历次数，可把数组看成环形，
设H(X):
H(a[1])=1,
H(x)=(x-a[1]+1+n)%n x<>a[1]
代码如下，复杂度为遍历2次：

#include <iostream.h>
#include <string.h>
#include <stdlib.h>

#define H(x,a1,n) (x-a1+1+n)%n

unsigned int find_lost(const int* source, const length) {
int h;
int i;
int ret=-1;
int *a=(int *)malloc(length*sizeof(int));
for(i=0;i<length;i++)
a[i]=0; // 存放hash值
a[1]=*(source+1); // 存放hash值
// H(x)=(x-a[1]+1+n)%n x<>a[1]
for(i=2;i<length;i++) {
h=H(*(source+i),*(source+1),length);
a[h]=*(source+i);
}
for(i=0;i<length;i++) {
if (a[i]==0)
break;
}
free(a);
return a[(i-1+length)%length]+1;
}

void main() {
int a[]={-1, 33, 32, 35, 31, 34};
cout<<find_lost(a,6)<<endl;
system("PAUSE");
}


[解决办法]
由题目可知数组里的数字是连续不重复的，所以前N项和很容易求得。
遍历整个数组（从第二个开始，-1不算），求出数组的和total，顺便求出最小值min。结果就是(min+min+length-1)*length/2-total.前N项和减去前N-1项和就是要找的那一项。
最小值没有被改变保证了找到的最小值一定是正确的。如果数值很大可以采用64位数o(∩_∩)o。时间O(n)，空间O(1).
这个题目貌似微软面试题的翻版。。。
[解决办法]
xlfddlfd的算法很好,没有比这更好的了,呵呵.

如果把问题扩展一下,针对任何位数的整数(32位,64位,128位,...),为了限制空间的使用,可以采取Jamesonang的方法.令中间变量永远不超过64位.

另外,使用以下办法,通过一次遍历就可以解决问题:
设S(k)为前k个数的和,min(k)为前k个数的最小值,a(k)为第k个数.
1.令S(1) = 0,min(1) = a(1)
2.对于任意k>=1,
如果min(k) <= a(k+1),
令S(k+1) = S(k) + a(k+1) - min(k),
min(k+1) = min(k);
否则
令S(k+1) = S(k) + k*(min(k) - a(k+1)),
min(k+1) = a(k+1);
3.lost = total - S + min // S与min是最后的和与最小值