今天在程序员面试题中，碰到一个有意思的题目：数组a[N]，存放了1至N-1个数，其中某个数重复一次，现在要求找出重复的数字且程序时间复杂度必须为O（N）。乍一看，如果不计时间复杂度和空间复杂度程序比较容易编写，但是考虑时间和空间复杂度，笔者首先想到的是用“哨兵”的经典方法。程序如下：
1 /************************************************************************/ 2 /* 功能：数组a[N],存放了1至N-1个数其中某个数重复一次,找出被重复的数字.时间复杂度必须为o（N） 3 /* 作者：ZL 4 /* 日期：2018-04-08 14:38 5 /************************************************************************/ 6 7 #include <stdio.h> 8 9 10 int do_dup(int a[],int n); 11 12 int main(void) 13 { 14 int a[5]={1,2,3,2,4}; 15 int data=0; 16 int n=5; 17 int i; 18 data=do_dup(a,n); 19 printf("data=%d ",data); 20 for (i=0;i<5;i++) 21 { 22 printf("%d ",a[i]); 23 } 24 25 26 } 27 28 29 int do_dup(int a[],int n) 30 { 31 int temp; 32 while(a[0]!=a[a[0]]) //a[0] 用作“哨兵” 33 { 34 temp=a[0]; 35 a[0]=a[temp]; 36 a[temp]=temp; 37 } 38 return a[0]; 39 40 41 }
程序在VC++6.0运行的结果如下图所示：
从结果中可以看出找到了数组重复数字，时间复杂也为O（N），却改变了数组原本的值，所以程序还需要改进，笔者借鉴网友提供的思路，用数学中假金条思想，将1到N-1个数看做是重量不同的金条，其中有一个是重复的，现在我们生产出1到N-1个不同重量，无重复的金条，然后将两组金条的重量加和，相减求出重量的差值，在用第1到N-1中最大的数（N-1）减去差值，就求出了需要找到重复数字。
例如：{1,2,3,3,4}这五个数，可以看做是{1,2,3,4}这四个数中插入了3这个数字，按照上述描述，我们产生{1,2,3,4,5}这五个数，可以看做是{1,2,3,4}中插入了5这个数字，将两组数加和，求出差值2，在用5减去2求得重复数字3。改进后的程序如下所示：
1 /************************************************************************/ 2 /* 功能：数组a[N],存放了1至N-1个数其中某个数重复一次,找出被重复的数字.时间复杂度必须为o（N） 3 /* 作者：ZL 4 /* 日期：2018-04-08 14:38 5 /************************************************************************/ 6 7 #include <stdio.h> 8 9 10 int do_dup(int a[],int n); 11 12 int main(void) 13 { 14 int a[5]={1,2,3,2,4}; 15 int data=0; 16 int n=5; 17 int i; 18 data=do_dup(a,n); 19 printf("data=%d ",data); 20 for (i=0;i<5;i++) 21 { 22 printf("%d ",a[i]); 23 } 24 25 26 } 27 28 29 int do_dup(int a[],int n) 30 { 31 int sum1=0,sum2=0; 32 int j; 33 for (j=0;j<n;j++) 34 { 35 sum1+=(j+1); 36 sum2+=a[j]; 37 } 38 return n-(sum1-sum2); 39 40 41 }
程序在VC++6.0运行的结果如下图所示：
改进后的程序，没有破坏原来的数组值，比上一个程序好。