求兩個有序整型數組元素和的第K大值

今天與人讨論問題，發現一個很有意思的題目：給定兩個有序的整型數組，要求在最優的情況下找到兩個數組元素求和後的第K大的值。

1、剛開始遇到這個問題，我直覺的想法就是配置設定一個數組儲存兩個數組元素的和，然後利用找有序數組中第K大元素的方法進行求解。然後分析了一下時間和空間複雜度，假設原始的兩個有序數組分别為A和B，對應的長度為m和n，那麼A和B中元素和就有m*n個，即我們需要配置設定一個新的數組C[m*n]儲存對應的元素和，填滿C數組的時間開銷為O(m*n)，然後在C中找第K大的元素，最快的時間複雜度為線性的，是以該方案的時間複雜度為O(m*n)，空間複雜度為O(m*n)。

如果m和n很大時，時間複雜度與空間複雜度都會很大，那麼我們能不能進行優化呢？一般我們求解一個數組中的元素都會采用“二分”的方法，那麼我們這個題目能不能采用這種政策呢？

2、答案是肯定的。因為A和B是兩個有序數組，是以A[0]+B[0]會是所有和的最小值，不妨記為min，同時，A[m-1]+B[n-1]對應所有和的最大值，不妨記為max，那麼我們要求的第K大值肯定在[min, max]區間中，我們不妨設第K大的值為C[K]，是以我們可以在區間[min, max]通過二分查找C[K]，因為[min, max]之間可能有很多重複元素，是以我們在查找C[K]的過程中可以通過判斷區間中有多少元素大于這個C[K]。如果比C[K]大的元素小于K個，而且比其小的元素也不到m*n-K個，那麼C[K]就是我們要求的值。如果比C[K]大的元素超過K個，那麼我們就隻需要在[mid, max]中找第K大的元素。如果比C[K]大的元素小于K個，那麼需要在[min, mid-1]中找第(K-Count(C[K] + mid))大的元素。這樣原問題就轉化為統計多少個數的和大于C[K]。

對于這個問題，可以采取周遊其中一個數組的方式，假如周遊數組A，然後利用二分在B中找C[K]-A[i]對應的元素，進而計算出相應的個數。因為A，B有序，是以如果找到A[i]+B[j]>C[K]，那麼A[p] + B[j] (i<p<=m)都會大于C[K]，同理，A[i] + B[q] (j<q<=n)都會大于C[K]。利用這個規則可以簡化我們的計數。

程式JAVA源代碼如下：

<span style="white-space:pre">	</span>public int getKthSum(int[] A, int[] B, int K) {
		if(A.length == 0 && B.length == 0)
			return 0; 
		if(A.length == 0) 
			return K>1 ? B[K-1] : 0;
		if(B.length == 0)
			return K>1 ? A[K-1] : 0;
		if(K == 0)
			return 0;
		int m = A.length - 1;
		int n = B.length - 1;
		int min = A[0] + B[0], max = A[m] + B[n];
		while(min < max) {
			int mid = (max + min) >>> 1;
			int count = Count(mid, A, m, B, n);
			if(count >= K) {
				min = mid + 1;
			} else {
				max = mid;
			}
		}
		return min;
	}
	
	/**
	 * 計算A和B的和中比value大的元素的個數有多少
	 * @param value
	 * @return
	 */
	public int Count(int value, int[] A, int m, int[] B, int n) {
		int count = 0;
		for(int i=0, j=n; i<=m && j>=0;) {
			if(A[i] + B[j] > value) {
				count += m - i + 1;  //因為A[p]+B[j]>value, i<p<=m
				j--;
			} else 
				i++;
		}
		return count;
	}
           

時間複雜度分析：二分法時間複雜度為O(log(max-min))，計算比C[K]大的元素個數的時間開銷為O(m+n)，因為兩者為嵌套關系，是以總的 時間複雜度為O((m+n)log(max-min))。

空間複雜度為O(1)。