数组a[N],存放了1至N-1个数,其中某个数重复一次。写一个函数,找出被重复的数字.时间复杂度必须为o(N)函数原型:

时间:2020-12-11 17:06:18

 

数组a[N],存放了1N-1个数,其中某个数重复一次。写一个函数,找出被重复的数字.时间复杂度必须为oN)函数原型:
int do_dup(int a[],int N)
我自己写的代码,也不知道正确与否,希望各位批评指正。
#include<iostream>
using namespace std;


int do_dup(int a[], int N)
{
 int *p = (int *)malloc(N*sizeof(int));
 for(int j=0; j<N; j++)
 {
  p[j]=0;
 }
 
 int result;
  for(int i=0; i<N; i++)
 {
  if (p[a[i]] == 0)
  {
   p[a[i]] = a[i];
   }
  else
  {
   result = a[i];
   cout << "the repeated num is " << result << endl;;
   return result;
  }
 }
 free(p);
 return 0;
}
int main()
{
 int a[5] = {2,3,4,4,1};
 do_dup(a, 5);
 return 1;
}

第二种答案:

int do_dup(int a[], int N)
{
 long sum1=0;
 long sum2=0;
   
 for(int j=0; j<N; j++)
 {
  sum1+=(j+1);
  sum2+=a[j];
 }
 
 return sum1-sum2;
}