算法题目--支配值数目

已知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.

评论

2 楼 SavageGarden 2008-08-29  

书中的C版的解法

int dominance_count(int f[],int g[],int m,int n){
	int index_f, index_g;
	int count;
	
	count = index_f = index_g=0;
	while (index_f <m && index_g <n){
		if (f[index_f] <= g[index_g]){
			index_f++;
		}else{
			index_g++;
			count += m-index_f;
		}
	}
	return count;
}

因为m,n分别为f,g的长度，fedora8下gcc编译通过

1 楼 SavageGarden 2008-08-29  

我的方法

public static void Gt_Count(int[] arrayA,int[] arrayB) {
		if(arrayA.length > 0 && arrayB.length > 0) {
			int count = 0;
			for(int i = 0;i < arrayB.length;i++) {
				for(int j = 0;j< arrayA.length;j++) {
					if(arrayA[j] <= arrayB[i]){
						continue;
					}else{
						count += arrayA.length-j-1;
					}
				}
			}
			System.out.println(count);
		}
	}