名題精選百則_題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++;
}
沒有留言:
張貼留言