小提一下,其實很多面試題目,會以 binary search 及字串處理之變化做為題目。自然的 binary search 前提條件必須是 array 有排序過,所以不少面試會以「已有一陣列,由小到大排序好的陣列」,這前提做為探討,本文做點整理。

首先,由冼鏡光老師所著之名題精選百則-技巧篇,第一章序曲裡有些也是基於這前提,由於該書版權問題,所以只會敘述裡面提到,相關的題目(前四點都是),解法有興趣的話可翻閱該書做參考。其他部份是筆者目前聽過的題目或加以想像的題目,我也不保證做法會是最好的。

 

[1] 最長平台 (名題百則)

 

已排序陣列,int arr[] = {12,2,3,3,3,4,5,5,6,6,6,6};

上面相同數字最多的是 6 ,共計 4 個,最長平台就是 4。

限制:變數愈少愈好、每個元素只查一次、敘述愈少愈好。

 

[2] 支配值數目 (名題百則)

 

已排序兩陣列,int f[] = {1,3,5,7,9},int g[] = {2,3,4,7,8};

求出 f[] 中每個元素比 g[] 中,每個元素大的個數之總數。如

g[0] =2 , f[] 中比 g[0] 大的有 4 個;g[1]=3, f[] 中比 g[1] 大的有 3 個;依此類推,最後算出來的支配數 = 4+3+3+1+1=12。

 

[3] 等值數目 (名題百則 )

 

已排序兩陣列,且此兩陣列裡的元素各自不會重覆,如 int f[] = {1,2,3,4} , int g[] = {2,4,6,8}

求 f[] g[] 裡面,有幾個元素是相同的。這例子而言,f, g 都有 2 和 4,共兩個,故等值數目 = 2。

 

[4] 兩陣列最短距離 ( 名題百則 )

 

已排序兩陣列, int f[] , int g[],等效要求下面程式碼

 

Code Snippet
  1. int mindist(int *f , int m , int * g , int n)
  2. {
  3.     int dist = abs(f[0] - g[0]);
  4.     int i, j, tmp;
  5.     for(i=0; i<m; ++i)
  6.         for(j=0; j<n; ++j)
  7.             if( (tmp = abs(f[i]-g[j])) < dist)
  8.                 dist = tmp;
  9.     return dist;
  10. }

 

上述是 O(m * n),但實際上會有更好的做法 O(m + n)

 

[5] 有幾個相異元素 (面試題)

假設一排序好之陣列 int arr[] = {1,1,2,2,2,2,3,4,4,5,5,5,8,8}; 裡面相異元素有 6 個。

 

Code Snippet
  1. int diff_count(int * arr, int n)
  2. {
  3.     int i, cnt=1;
  4.     for(i=1 ; i<n; ++i)
  5.         cnt+=(arr[i]!=arr[i-1]);
  6.     return cnt;
  7. }

 

延伸 : 若陣列沒排序過,怎麼求相異元素個數?

 

 

[6] 移除相同元素 (面試題)

 

假設一排序好之陣列 int arr[] = {1,1,2,2,2,2,3,4,4,5,5,5,8,8}, 寫出 int remove_same(int * arr, int n); 移除相同之元素,最後傳回移除後之元素個數。

以上為例,最後呼叫後變成 arr[] = {1,2,3,4,5,8} ( 後面有沒有都不管),然後傳回 6 。

 

Code Snippet
  1. int remove_same(int * arr, int n)
  2. {
  3.     int i=0, j=1; // j=0 to defect n==1
  4.     while(j<n){
  5.         // find next different element between index i and index j
  6.         while(j< n && arr[j]==arr[i]) ++j;
  7.         // assign
  8.         if(j<n)    arr[++i] = arr[j],++j;
  9.     }
  10.     return ++i;
  11. }

 

延伸:若陣列沒排序過,怎麼做移除動作?

 

[7] 找出某陣列有幾個元素個數

 

假設一排序好之陣列 int arr[] = {1,2,2,3,3,3,3,4,5,5},怎麼求得元素 3 有 4 個?

 

這題目其實變化很多,但原則上都是從二分搜尋法來的,而且做法變化也很多!

 

[解 1]  polling 。 

Code Snippet
  1. int find_key_cnt(int * arr, int key, int n)
  2. {
  3.     int i, c;
  4.     for(i=c=0; i<n; ++i) if(key==arry[i]) ++c;
  5.     return c;
  6. }

 

[解 2] 傳統二分法,找到 key 後往左右兩邊跑。

Code Snippet
  1. int find_key_cnt(int * arr, int key, int n)
  2. {
  3.     int low=0, up=n-1, mid, i, c=0;
  4.     while(low<=up){
  5.         mid = (low+up)>>1;
  6.         if(arr[mid]==key)  break;
  7.         else if(arr[mid]>key) up = mid-1;
  8.         else low = mid+1;
  9.     }
  10.     if(low>up) return 0; // can't find key value    
  11.     for(i=mid; i<n && arr[i]==key; ++i) ++c; // 往右邊計數
  12.     for(i=mid-1; i>=0 && arr[i]==key; --i) ++c; // 往左邊計數
  13.     return c; // 傳回去    
  14. }

 

[解 3] 遞迴式二分法

(0) 如果重覆太多的時候才有意義, 適用於大批量, 小批量甚至用 polling 就行。

(1) 假設二分找到最後,low = 100 , mid = 500 , up = 900,代表 arr[101:899] 都有可能是 key value。

(2) 所以再抓 arr[low+1 , mid-1] , 找 key value ; 抓 arr [ mid+1 , up -1]  , 找 key value。重覆 (1) (2) 步驟。

(3) 當 (up - mid) 距離小時,比如說小於 20  或 30 時 (閥值),才用上述的左右 polling 。

實作落落長,效率不見得比較快,有興趣自己搞。

 

[解 4] 

之前有寫過,找第一個 key value 、找最後一個 key value 之二分搜尋法 ( [面試] binary search ) ,目前在想,差一點就執行兩次 ( 都是 O(logn) ),搞剛一點就把這兩個併成一個 loop ,一起找,但不保證併成一個 loop 效能一定會提昇。

一樣,實作落落長,效率不見得比較快,有興趣自己搞。

 

其他的,想到再補。

arrow
arrow
    全站熱搜

    edisonx 發表在 痞客邦 留言(2) 人氣()