2011年9月30日 星期五

[C++ 考題] 請寫出函數可以移除整數 Array 中重複的元素並回傳 Unique 元素的個數


題目 :
請參照下面API Interface 設計該API 可以將傳入的整數Array 重複的元素移除, 並回傳Unique 元素的個數, API Interface 如下 :
  1. /* 
  2. * 移除 array 中重複的值, 並回傳unique 的元素數目. 
  3. *  array : 欲移除重複元素的矩陣. 
  4. *  size : 傳入矩陣 array 的 元素個數. 
  5. */  
  6. int simpleTest2(int array[], int size);  

解題說明 :
1. 首先要考慮的就是邊界值的問題, 假如矩陣一個元素都沒有. 那根本不需要計算, 就直接返回 0 回去.
2. 接著以矩陣的第一個元素(第零個位置)為參考並使用一個整數 insert 變數(預設是一)紀錄以插入的 unique 元素, 然後將第二個元素與第一個元素比較, 如果不一樣, 就將之置放於矩陣由insert 變數指定的位置(目前是一, 所以擺到第一個位置), 並將 insert 加一.
3. 接下來就拿第三個元素跟前面已比較過的 unique 元素比較, 如果都不同就將之置於 insert 變數所指的位置上, 並將 insert 變數加一. 並以此類推.
4. 以上述流程走訪傳入矩陣的每個元素, 比較完畢後將 insert 所指的位置設為 null pointer, 並回傳 insert 完成函數呼叫.

* 範例代碼 :
  1. int simpleTest2(int array[], int size) {  
  2.     if(size<0) { // 如果傳入矩陣為空, 則回傳0  
  3.         return 0;  
  4.     }  
  5.     int insert = 1;  
  6.     bool flag ;  
  7.     for(int i=1; i
  8.         flag = true;  
  9.         for(int j=0; j
  10.             if(array[j] == array[i]) {  
  11.                 /*如果出現與前面unique重複則跳開比較*/  
  12.                 flag = false;                 
  13.                 break;  
  14.             }  
  15.         }  
  16.         if(flag) { /*沒有出現與前面unique重複的值*/  
  17.             array[insert++] = array[i];           
  18.         }  
  19.     }  
  20.     array[insert] = NULL;  
  21.     return insert;  
  22. }  
* 呼叫API 範例代碼 :
  1. int p[7] = {1,2,1,4,2,6,1};  
  2. int sc = simpleTest2(p, 7);  
  3. printf("Unique Count: %d\n",sc);  
  4. for(int i=0;i<7; i++) {  
  5.     if(p[i]!=NULL) {  
  6.         printf("%d ",p[i]);  
  7.     } else   
  8.         break;  
  9.     }  
  10.     printf("\n");  
  11. }  

執行結果 :
Unique Count: 4
1 2 4 6 <共有4 unique 個元素>

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...