文章目錄
已知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
利用数组已经排好序的这个特性，可以写出高效的程序.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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));
}
}
|
