算法百题002:支配值数目

    技术2022-05-12  19

    声明:本题源代码为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


    最新回复(0)