1.数组a[N]，存放了1至N-1范围内N个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o（N）函数原型：
int do_dup(int a[],int N)
算法：
a1+a2+ ......+aN=1+2+3+..+x+..+(N-1)+(N-x);
s1=a1+a2+....+aN;
s2=1+2+3+...+N;
x=s1-s2+N;
#####################################################
/***************************
Author:xiaoshou
Description:main.c
***************************/
#include
int do_dup(int a[],int N);
int main(void)
{
int N=10;
int i;
int res;
int a[]={1,2,3,4,5,2,6,7,8,9};
for(i=0;i
{
printf("a[%d]=%d\n",i,a[i]);
}
res=do_dup(a,N);
printf("dup a[]=%d\n",res);
return 0;
}
int do_dup(int a[],int N)
{
int s1=0,s2=0;
int i,x;
for(i=0;i
{
s1+=a[i];
s2+=i+1;
}
x=s1-s2+N;
return x;
}
################################################
/***************************
Author:xiaoshou
Description:Makfile
***************************/
CC=gcc
CFLAGS= -Wall
OBJ=offer
$(OBJ):main.c
$(CC) $(CFLAGS) -o $@ $<
clean:
-rm -f *.o $(OBJ)
##################################################
运行情况：
[root@MagicLinux offer]# ./offer
a[0]=1
a[1]=2
a[2]=3
a[3]=4
a[4]=5
a[5]=2
a[6]=6
a[7]=7
a[8]=8
a[9]=9
dup a[]=2
阅读(1794) | 评论(0) | 转发(0) |
