声明：本题源代码为fduan原创，转载请注明出处。
题目：已知f[]和g[]两数组已按升序排列，求f[]中每个元素比g[]中元大的个数总和。
思路一：按最常规的想法，通过两重循环，依次从g中找比f中每个元素大的个数，该方法未利用f、g已排序的特点，时间复杂度为O(m * n)
/* * Function: GT_COUNT_V1 *----------------------------------- * brute force search approach. */ int gt_count_v1( int f[], int n, int g[], int m ) { int cnt = 0; for( int i = 0; i < n; ++i ) { for( int j = 0; j < m; ++j ) { if( f[i] > g[j] ) ++cnt; else break; } } return cnt; }
思路二：充分利用f和g已排序的特点，将复杂度将至O(m+n)。思路一之所以复杂度高，是由于 j 索引反复回溯。如果引入变量记录g中当前待比较元素的位置，就可避免回溯。同时注意由于num变量中统计的只是从当前比较位置开始的小于f当前元素的个数，因此在求总和时需要累加。
/* * Function: GT_COUNT_V2 *-------------------------------------------------- * Time complexity: O( m + n) */ int gt_count_v2( int f[], int n, int g[], int m ) { // current position of the G's element to compare int idx = 0; // the number of elements in G which are less than the current element in F int num = 0, prev_num = 0; int sum = 0; for( int i = 0; i < n; ++i ) { num = 0; for( int j = idx; j < m; idx = ++j ) { if( f[i] > g[j] ) ++num; else break; } if( idx <= m ) { prev_num += num; } sum += prev_num; } return sum; }
题目出处：M.Rem.Small Programming Exercise 2. Science of Computer Programming, Vol.3(1983), pp.313--319
