在101个数字中查找重复数字

题目：有101个数字，每个数字的值均介于0～99之间。这101个数字中只有两个数字是重复的，请你找出来重复的数字和相应的位置。

随机产生数组：

int i,j,Number[101],Temp[101];
 int left=0,right=0;
 srand((unsigned)(time(NULL)));
 for(i=0;i<101;i++)     //初始化数组
 {
  Number[i] = 9999;
  Temp[i] = 9999;
 }

 for(i=0;i<101;i++)     //随机产生101个数字
 {
  j = rand()%101;
  while(Number[j] != 9999)
   j = rand()%101;
  if(i == 100)
  {
   right = rand()%100;
   Number[j] = right;
  }
  else
   Number[j] = i;
 }

方法一：

for(i=0;i<101;i++)     //查找重复数字及位置
 {
  j = Number[i];
  if(Temp[j] == 9999)
   Temp[j] = i;//存储每个数字的相应下标
  else
  {
   left = Temp[j]; //重复数字的第一个位置
   right =i;  //重复数字的第二个位置
   break;
  }
 }

这里主要是有一个临时数组，所以只要逐个的扫描数组就可以了，最坏的情况是101次。但是，这是拿空间来换时间，多出来一个大小为101的临时数组。

 方法二：

while(1)//查找重复数字
 {
  value = low + ((high - low)/2);
  for(i = 0;i<101;i++)  
  {
   if( Number[i] > value)
    right++;
   if( Number[i] < value)
    left++;
  }
  if(right > (99 - value))
  {
   low = value ;
   right = 0;
   left = 0;
   //printf("High\n");
  }
  else if(left > (value-0))
  {
   high = value ;
   right = 0;
   left = 0;
   //printf("Low\n");
  }
  else if((right == (99-value)) && (left == (value-0)))
   break;
  if(high == low)
   break;
 }

这里采用的是折半查找的方法，最坏的情况是7*101 ＝ 707次就可以找到重复的值了。

如果还要打印两个重复数字的位置的话，再扫描一下数组就可以了，最坏再加上101次。

方法二的打印算法：

j = 0;
 for(i = 0;i<101;i++)//扫描数组，找到重复数字所在的两个位置
 {
  if(Number[i] == value)
  {
   printf("Number[%d]\t",i);
   j++;
  }
  if(j == 2)
  {
   printf("\n");
   break;
  }
 }

完整源代码：

void FindNumber1()
{
 int i,j,Number[101];
 int low = 0,high = 100,value,left=0,right=0,key=0;
 srand((unsigned)(time(NULL)));
 for(i=0;i<101;i++)      //初始化数组
  Number[i] = 9999; 
 for(i=0;i<100;i++)      //随机产生100个数字
 {
  j = rand()%101;
  while(Number[j] != 9999)
   j = rand()%101;
  Number[j] = i;
 }
 j = rand()%100; //产生重复数字
 for(i=0;i<101;i++)
 {
  if(Number[i] == 9999)//插入重复数字
   Number[i] = j;
  printf("%d\t",Number[i]);//打印数组元素
  if(i != 0 && i%5 == 4)
   printf("\n");
 }
 //printf("%d\n",j);
 while(1)//查找重复数字
 {
  value = low + ((high - low)/2);
  for(i = 0;i<101;i++)  
  {
   if( Number[i] > value)
    right++;
   if( Number[i] < value)
    left++;
  }
  if(right > (99 - value))
  {
   low = value ;
   right = 0;
   left = 0;
   //printf("High\n");
  }
  else if(left > (value-0))
  {
   high = value ;
   right = 0;
   left = 0;
   //printf("Low\n");
  }
  else if((right == (99-value)) && (left == (value-0)))
   break;
  if(high == low)
   break;
 }
 printf("\nNumber = %d\t",value);
 j = 0;
 for(i = 0;i<101;i++)//扫描数组，找到重复数字所在的两个位置
 {
  if(Number[i] == value)
  {
   printf("Number[%d]\t",i);
   j++;
  }
  if(j == 2)
  {
   printf("\n");
   break;
  }
 }
}
void FindNumber2()
{
 int i,j,Number[101],Temp[101];
 int left=0,right=0;
 srand((unsigned)(time(NULL)));
 for(i=0;i<101;i++)     //初始化数组
 {
  Number[i] = 9999;
  Temp[i] = 9999;
 }

 for(i=0;i<101;i++)     //随机产生101个数字
 {
  j = rand()%101;
  while(Number[j] != 9999)
   j = rand()%101;
  if(i == 100)
  {
   right = rand()%100;
   Number[j] = right;
  }
  else
   Number[j] = i;
 }

 for(i=0;i<101;i++)     //打印数组
 {
  printf("%d\t",Number[i]);
  if(i != 0 && i%5 == 4)
   printf("\n");
 }

 for(i=0;i<101;i++)     //查找重复数字及位置
 {
  j = Number[i];
  if(Temp[j] == 9999)
   Temp[j] = i;//存储每个数字的相应下标
  else
  {
   left = Temp[j]; //重复数字的第一个位置
   right =i;  //重复数字的第二个位置
   break;
  }
 }
 printf("\nNumber = %d\tNumber[%d]\tNumber[%d]\n",j,left,right);
}