2013年1月13日 星期日

[Q1-2]GT_COUNT

[SOURCE]
名題精選百則_題1.2

[INPUT]
two number set f[ ] and g[ ] which are sorted in increment order
ex. 
f =1,3,5,7,9  
g =1,4,5,8,10
lengthF= number of elements in f
lengthG= number of element in g
    
[OUTPUT]
f[j]>g[i] means "greater" , count totally "greater"
ex. 
g[0]→3,5,7,9→"greater" count is 4
g[1]→5,7,9→"greater" count is 3
g[2]→7,9→"greater" count is 2
g[3]→9→"greater" count is 1
g[4]→none→"greater" count is 0

therefore, totally "greater" is 4+3+2+1+0=10

[THINK]
f, g都是已經排序好的數列
所以當 f[j]>g[i] 時表示f[j]之後的數也都會大於g[i]
"greater"個數為 lengthF-j
當 f[j]<=g[i] 時,往f[j]的下一個元素 f [j+1]比較

[SCv1]
//i is index of g
//j is index of f
//sum is the result    
    for(i=0;i<lengthG;i++){
      for(j=idx;j<lengthF;j++){
        if(f[j]>g[i]){
          tmpL=lengthF-j;
          idx=j;
          break;
        }        
      }
      if(j==lengthF)
        break;
      else
        sum=sum+tmpL;
    }

[SCv2]
//i is index of g
//j is index of f
//sum is the result    
    while(i< lengthG && j< lengthF){
      if(f[j]>g[i]){
        sum+=(lengthF-j);
        i++;
      }             
      else
        j++;
    }


沒有留言:

張貼留言