有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升序排列。对于1<=i,j<=k,求k个最小的(ai+bj)。要求算法尽量高效。

时间:2021-09-11 21:14:39

有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升序排列。对于1<=i,j<=k,求k个最小的(ai+bj)。要求算法尽量高效。

int *min_k(int *A, int *B, int len1, int len2, int k) {
	if (A == NULL || B == NULL || k <= 0)
		return NULL;
	int i, j;
	int *tmp = new int[k];
	i = len1;
	j = len2;
	while (i > 0 && j > 0) {	//当前情况是否满足条件
		//移动哪一个数组的元素
		if (A[i - 1] >= B[j - 1]) {
			//是否可移动
			if ((i - 1) * j >= k)
				i--;
			else
				break;
		} else {
			if ((j - 1) * i >= k)
				j--;
			else
				break;
		}
	}
	int count = 0;
	//A[i-1]>B[i-1],则先计算B元素的和,避免A[i-1]算入
	if (A[i - 1] > B[j - 1]) {
		int p, q;
		for (p = 0; p < i; p++) {
			for (q = 0; q < j; q++) {
				if (count < k) {
					cout << "A:" << A[p] << " B: " << B[q] << " ";
					tmp[count++] = A[p] + B[q];
				} else
					break;
			}
		}
	} else {
		int p, q;
		for (p = 0; p < j; p++) {
			for (q = 0; q < i; q++) {
				if (count < k) {
					cout << "B:" << B[p] << " A: " << A[q] << " ";
					tmp[count++] = B[p] + A[q];
				} else
					break;
			}
		}
	}
	return tmp;
}