歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

樂視TV2015校園招聘A卷第二大題(中國科學院大學站)

題目描述:給定數組A,大小為n,數組元素為1到n的數字,不過有的數字出現了多次,有的數字沒有出現。請設計算法和程序,統計哪些數字沒有出現,哪些數字出現了多少次。能夠在O(n)的時間復雜度,O(1)的空間復雜度要求下完成麼?(思路和代碼)

參考:http://www.linuxidc.com/Linux/2015-01/111268.htm

主要思路:四次遍歷。

第一遍歷:確定是否全部數字都一樣,例如出現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;
 }
}

Copyright © Linux教程網 All Rights Reserved