乐视TV2015校园招聘A卷第二大题（中国科学院大学站）

乐视TV2015校园招聘A卷第二大题（中国科学院大学站）

题目描述：给定数组A，大小为n，数组元素为1到n的数字，不过有的数字出现了多次，有的数字没有出现。请设计算法和程序，统计哪些数字没有出现，哪些数字出现了多少次。能够在O(n)的时间复杂度，O(1)的空间复杂度要求下完成么？（思路和代码）

参考：

主要思路：四次遍历。

第一遍历：确定是否全部数字都一样，例如出现n个1或者n个2的情况。若一样，直接输出结果，否则进入第二次遍历。（这是我看了参考后添加的）

第二次遍历：对所有]i执行A[i] = A[i] *n

第三次遍历：对所有i执行++A[A[i]/n]

第四次遍历：对所有i执行A[i] = A[i] % n

这样，A[i]的值为i在数组中出现的次数。

解释：

1、由于第一次遍历，保证了后序步骤中任意元素出现的次数不可能超过n。

2、先执行A[i]=A[i]*n，让取余的时候A[i]本身的值不会对i出现的次数产生影响。

3、然后执行++A[A[i]/n]，对A[i]本来的位置不断增加1，但绝不会超过n，所以每个i出现的次数，就是A[i]对n取余。

代码如下：

void repetitions(int a[], int n)
{
 int i = 1;
 int frequencey = 0;
 int element;
 int temp;
 
 temp = a[1];
 for(i = 2; i <= n; ++i){
  if(a[i] != temp)
   break;
 }

 if(i == n + 1 && a[i-1] == temp)
 {
  cout << temp << "出现了" << n << "次,其余数字没有出现" << endl;
  return;
 }

 for(i = 1; i <= n; ++i)
  a[i] *= n;
 for(i = 1; i <= n; ++i){
  ++a[a[i]/n];
 }

 for(i = 1; i <= n; ++i){
  cout << i << "出现了" << a[i] % n << "次" << endl;
 }
}

本文永久更新链接地址：