小提一下,其實很多面試題目,會以 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[],等效要求下面程式碼
- int mindist(int *f , int m , int * g , int n)
- {
- int dist = abs(f[0] - g[0]);
- int i, j, tmp;
- for(i=0; i<m; ++i)
- for(j=0; j<n; ++j)
- if( (tmp = abs(f[i]-g[j])) < dist)
- dist = tmp;
- return dist;
- }
上述是 O(m * n),但實際上會有更好的做法 O(m + n)
[5] 有幾個相異元素 (面試題)
假設一排序好之陣列 int arr[] = {1,1,2,2,2,2,3,4,4,5,5,5,8,8}; 裡面相異元素有 6 個。
- int diff_count(int * arr, int n)
- {
- int i, cnt=1;
- for(i=1 ; i<n; ++i)
- cnt+=(arr[i]!=arr[i-1]);
- return cnt;
- }
延伸 : 若陣列沒排序過,怎麼求相異元素個數?
[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 。
- int remove_same(int * arr, int n)
- {
- int i=0, j=1; // j=0 to defect n==1
- while(j<n){
- // find next different element between index i and index j
- while(j< n && arr[j]==arr[i]) ++j;
- // assign
- if(j<n) arr[++i] = arr[j],++j;
- }
- return ++i;
- }
延伸:若陣列沒排序過,怎麼做移除動作?
[7] 找出某陣列有幾個元素個數
假設一排序好之陣列 int arr[] = {1,2,2,3,3,3,3,4,5,5},怎麼求得元素 3 有 4 個?
這題目其實變化很多,但原則上都是從二分搜尋法來的,而且做法變化也很多!
[解 1] polling 。
- int find_key_cnt(int * arr, int key, int n)
- {
- int i, c;
- for(i=c=0; i<n; ++i) if(key==arry[i]) ++c;
- return c;
- }
[解 2] 傳統二分法,找到 key 後往左右兩邊跑。
- int find_key_cnt(int * arr, int key, int n)
- {
- int low=0, up=n-1, mid, i, c=0;
- while(low<=up){
- mid = (low+up)>>1;
- if(arr[mid]==key) break;
- else if(arr[mid]>key) up = mid-1;
- else low = mid+1;
- }
- if(low>up) return 0; // can't find key value
- for(i=mid; i<n && arr[i]==key; ++i) ++c; // 往右邊計數
- for(i=mid-1; i>=0 && arr[i]==key; --i) ++c; // 往左邊計數
- return c; // 傳回去
- }
[解 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 效能一定會提昇。
一樣,實作落落長,效率不見得比較快,有興趣自己搞。
其他的,想到再補。
留言列表