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 個元素>

沒有留言:

張貼留言

[ Java 文章收集 ] 局部敏感哈希 (Locality-Sensitive Hashing, LSH) 方法介紹

Source From  Here   Preface   本文主要介紹一種用於海量高維數據的近似最近鄰快速查找技術—— 局部敏感哈希  ( Locality-Sensitive Hashing, LSH ),內容包括了 LSH 的原理、LSH 哈希函數集、以及 LSH 的一...