两个已排序数组的第K大元素

两个已排序数组A[m]、B[n]，求两者所有元素的第k大的元素

方法一

直接merge两个数组，然后求第K大的元素

方法二

使用计数器h记录当前已经找到第m大的元素；
使用两个指针pA和pB，分别指向数组A和B；
如果A当前元素小，pA++，m++;
如果B当前元素小，pB++，m++;
当m==k，得到答案。
O(k)时间，O(1)空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private:
	static int find_kth(std::vector<int>::const_iterator A, int m,
						std::vector<int>::const_iterator B, int n,
						int k) {
        int i = 0;
        int j = 0;
        int h = 1;
        
        if (0 == m) return B[k - 1];
        if (0 == n) return A[k - 1];
        if (1 == k) return min(A[0], B[0]);
        
        while (i<m && j<n) {
            if (A[i] <= B[j]) {
                i++;
                h++;
                if (h == k) return A[i - 1];
            } else {
                j++;
                h++;
                if (h == k) return B[j - 1];
            } 
        }
	}

方法三

充分利用有序，每次排除k/2个元素，使用递归
·当A或B为空时，直接返回B[k-1]或A[k-1]
·当k==1时，返回min(A[0], B[0])
·当A[k/2 - 1] == B[k/2 - 1]时，返回A[k/2 - 1]或B[k/2 - 1]
假设A和B的元素个数都大于k/2，
·if (A[k/2 - 1] < B[k/2 - 1]) 排除A数组的k/2个元素。
·else if (A[k/2 - 1] > B[k/2 - 1]) 排除B数组的k/2个元素。
·else 找到了第k大的元素，直接返回A[k/2 - 1]或B[k/2 - 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
	double findMedianSortedArrays(const vector<int>& A, const vector<int>& B) {
		const int m = A.size();
		const int n = B.size();
		int total = m + n;

		if (total & 0x1) {
			return find_kth(A.begin(), m,
							B.begin(), n,
							total/2 + 1);
		} else {
			return (
					find_kth(A.begin(), m,
							B.begin(), n,
							total/2) + 
					find_kth(A.begin(), m,
							B.begin(),n,
							total/2 + 1)
					) / 2.0;
		}
}

private:
	static int find_kth(std::vector<int>::const_iterator A, int m,
						std::vector<int>::const_iterator B, int n,
						int k) {
		if (m > n) return find_kth(B, n, 
								   A, m, 
								   k);
		if (m == 0) return *(B + k - 1);
		if (k == 1) return min(*A, *B);

		int ia = min(k/2, m);
		int ib = k - ia;
		if (*(A + ia - 1) < *(B + ib - 1)) {
			return find_kth(A + ia, m - ia,
				            B, n,
				            k - ia);
		} else if (*(A + ia - 1) > *(B + ib - 1)) {
			return find_kth(A, m,
				            B + ib, n - ib,
				            k - ib);
		} else {
			return *(A + ia - 1);
		}
	}
};

Comments

2016-03-07
▲