[Q1-3]EQ_COUNT

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

[INPUT]
two number set f[ ] and g[ ] which are sorted in increment order
ex. 
f =1,3,5,7,9  
g =1,5,6,8,10
lengthF= number of elements in f
lengthG= number of element in g

[OUTPUT]
f[j]=g[i] means "equal" , count totally "equal" value number
ex.
g[0]=f[0]=1
g[1]=f[2]=5

therefore, totally "equal" value number is 2

[THINK]
f, g都是已經排序好的數列
借用Q1-2的想法,f[idxF]==g[idxG]表示f[idxF], g[idxG]之前的數不用拿來做比較
分成3種情況
Case 1: f[idxF]==g[idxG]
Case 2: f[idxF]>g[idxG]
Case 3: f[idxF]<g[idxG]

Case 1就是我們想要的, count加1, f[ ]和g[ ]的idx都往後移

Case 2表示現在f[idxF]較大, 所以我們將g[ ]的idx往後移

Case 3表示現在g[idxG]較大, 所以我們將f[ ]的idx往後移

[SCv1]

//idxG is index of g
//idxF is index of f
    while(idxG< lengthG && idxF< lengthF){
      if(f[idxF]==g[idxG]){
        sum++;
        idxG++;
        idxF++;
      }             
      else if(f[idxF]>g[idxG]){
        idxG++;
      }
      else{   
        idxF++;
      }
    }

[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++;
    }