[C Programming] 支配值數目-延伸

延伸問題:
1.若f[]和g[]都有n個元素，試證明這個程式最多只會比較2n次。
2.如果f[]與g[]中有相同元素時，這個程式還正確嗎？為什麼？
3.請修改程式，把在g[]中小於每一個f[i]的元素都顯示出來。

個人解法:
1. 在程式中，每次比較的結果必定是f[]的index++，
    或者g[]的index++。
    所以最多可能產生的比較次數的狀況就是兩者都跑到底，也就是2n次。
    可能成立嗎？可以的XD
    只要考慮g[n-1]<f[n-1]<g[n]<f[n]這樣的情況，
    就可以保證兩邊都會跑到尾了。
2. f[]中有相同元素的時候程式不會影響，
   因為由小到大排序，當f[]如像11,12,12,12,13,13，g[]像8,12,13,14,15，
   我們找到第一個12去比較8時，仍然可以保證其後的值仍大於8。
   g[]的狀況也是一樣，因為比較都是一個一個去比的，
   f[]不夠大會找下一個來比，g[]不夠大也會找自己的下一個來比，
   所以不會影響程式的正確性。
3.我們可以另外產生一個陣列h[]來記錄。
   h[i]的值表f[i]是從g[]的第幾個值以前比較大。
   注意要控制迴圈的條件，如果因為g[]的序列先跑完的話，
   h[]要把後面的值補滿。(皆為n)

Code大概長這樣：

int gt_cnt(int f[], int g[], int h[], int m, int n)
{
 int cnt = 0, _fi = 0, _gi = 0, _hi = 0;
 while( (_fi < m) && (_gi < n) )
  if(f[_fi] <= g[_gi]) 
  { h[_fi] = _gi; _fi++; }
  else
  { cnt += m-_fi; _gi++; } 
 while( _fi < m ) 
  h[_fi++] = n;
 
 printf("For all elements in g[] ");
 printf("which are less than f[i]:");
 while( _hi < m )
 {
  _gi = 0;
  printf("\nf[%2d]: ", _hi);
  while( _gi < h[_hi])
   printf("%d ", g[_gi++]);
  _hi++;
 }
 return cnt;
}

執行結果像這樣子:

測資:
f[] = {1,3,5,7,9,10,11,12,13,15,17,18,19,20,21}
g[] = {5,6,7,8,9,10,12,13,18,19,20,21,22,23,24,25,26}
// Output
For all elements in g[] which are less than f[i]:
f[ 0]:
f[ 1]:
f[ 2]:
f[ 3]: 5 6
f[ 4]: 5 6 7 8
f[ 5]: 5 6 7 8 9
f[ 6]: 5 6 7 8 9 10
f[ 7]: 5 6 7 8 9 10
f[ 8]: 5 6 7 8 9 10 12
f[ 9]: 5 6 7 8 9 10 12 13
f[10]: 5 6 7 8 9 10 12 13
f[11]: 5 6 7 8 9 10 12 13
f[12]: 5 6 7 8 9 10 12 13 18
f[13]: 5 6 7 8 9 10 12 13 18 19
f[14]: 5 6 7 8 9 10 12 13 18 19 20
Count: 84