支配值数目

文章目錄

已知f[]与g[]两个整数数组，元素已经从小到大排列，请写一个程序，算出f[]中比g[]元素大的对数。换句话说，f[0]比g[]中多少个元素大，f[1]比g[]中多少元素大等，这些值的总和就是要求的答案。

例如，如果f[]中有1，3，5，7，9，而g[]中有2，3，4，7，8，比g[0]大的有f[1]~f[4], 比g[1]大的有f[2]~f[4]，比g[2]大的有f[2]~f[4]，比g[3]大的有f[4]，比g[4]大的有f[4]，因此答案是4 + 3 + 3 + 1 + 1 = 12

利用数组已经排好序的这个特性，可以写出高效的程序.

public class GTCount {
    public static int gtCount(int[] f, int[] g) {
        int i = 0;
        int j = 0;
        int result = 0;
        while (i < f.length && j < g.length) {
            if (f[i] > g[j]) {
                result += f.length - i;
                j++;
            } else {
                i++;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] f = {1, 3, 5, 7, 9};
        int[] g = {2, 3, 4, 7, 8};
        System.out.println(gtCount(f, g));
    }
}