2つのソート配列の中央値/K番目の大きな要素(Median of Two Sorted Arrays)

転入先 http://blog.csdn.net/zxzxy1988/article/details/8587244
並べ替えられた2つの配列(空の可能性がある)を指定し、両方のすべての要素のk番目に大きい要素を見つけます.もう1つのより具体的な形式は、すべての要素の中位数を見つけることです.この文章では、より一般的な問題だけを議論します.2つの配列のk番目の要素をどのように見つけるか.しかし、テストは2つの配列の中位数の問題で、Leetcode第4題です. Median of Two Sorted Arraysスキーム1:2つの配列に合計n要素があると仮定すると,O(n)時間とO(n)空間を用いる方法が明らかになる:merge sortの考え方で並べ替え,並べ替えられた配列からk-1と表記された要素を取り出すことが必要である.この方法は考えやすいですが、もっと良い方法はありませんか?シナリオ2:k番目の要素しか必要ないので、「ソート」のような複雑な操作は必要ありません.カウンタを使用して、現在m番目の大きな要素が見つかったことを記録することができます.同時に,2つのポインタpAとpBを用いて,それぞれAとB配列の最初の要素を指す.merge sortと同様の原理を用いて,配列Aの現在の要素が小さい場合,pA++,同時にm++である.配列Bの現在の要素が小さい場合、pB++であり、m++である.最終的にmがkに等しいとき,O(k)時間,O(1)空間という私たちの答えが得られた.しかし,kがnに近い場合,この方法はまだ時間がかかる.もちろん、kがn/2より大きいと、最大の要素から探すことができると判断できます.しかし、もし私たちがすべての要素の中位数を探していたら?時間はO(n/2)=O(n)のままです.もっと良い案はありますか?kから始めることを考えることができます.もし私たちが毎回k番目の要素の前にある要素を取り除くことができたら、私たちはk回行う必要があります.しかし、毎回半分を取り除くとしたら?したがって、このような二分的な考え方では、Assume that the number of elements in A and B are both larger than k/2,and if we compare the k/2-th smallest element in A(i.e.[k/2-1])and the k-th smallest element in B(i.e.B[k/2-1])、there are three results:(Becasue k can be odd or even number, so we assume k is even number here for simplicy. The following is also true when k is an odd number.)A[k/2-1] = B[k/2-1]A[k/2-1] > B[k/2-1]A[k/2-1] < B[k/2-1]if A[k/2-1] < B[k/2-1], that means all the elements from A[0] to A[k/2-1](i.e. the k/2 smallest elements in A) are in the range of k smallest elements in the union of A and B. Or, in the other word, A[k/2 - 1] can never be larger than the k-th smalleset element in the union of A and B.Why?We can use a proof by contradiction. Since A[k/2 - 1] is larger than the k-th smallest element in the union of A and B, then we assume it is the (k+1)-th smallest one. Since it is smaller than B[k/2 - 1], then B[k/2 - 1] should be at least the (k+2)-th smallest one. So there are at most (k/2-1) elements smaller than A[k/2-1] in A, and at most (k/2 - 1) elements smaller than A[k/2-1] in B.So the total number is k/2+k/2-2, which, no matter when k is odd or even, is surly smaller than k(since A[k/2-1] is the (k+1)-th smallest element). So A[k/2-1] can never larger than the k-th smallest element in the union of A and B if A[k/2-1] B[k/2-1] condition, which we should drop the elements in B.When A[k/2-1] = B[k/2-1], then we have found the k-th smallest element, that is the equal element, we can call it m. There are each (k/2-1) numbers smaller than m in A and B, so m must be the k-th smallest number. So we can call a function recursively, when A[k/2-1] < B[k/2-1], we drop the elements in A, else we drop the elements in B.We should also consider the edge case, that is, when should we stop?1. When A or B is empty, we return B[k-1]( or A[k-1]), respectively;2. When k is 1(when A and B are both not empty), we return the smaller one of A[0] and B[0]3. When A[k/2-1] = B[k/2-1], we should return one of themIn the code, we check if m is larger than n to garentee that the we always know the smaller array, for coding simplicy.

double findKth(int a[], int m, int b[], int n, int k) { //always assume that m is equal or smaller than n

    if (m > n) return findKth(b, n, a, m, k); if (m == 0) return b[k - 1]; if (k == 1) return min(a[0], b[0]); //divide k into two parts

    int pa = min(k / 2, m), pb = k - pa; if (a[pa - 1] < b[pb - 1]) return findKth(a + pa, m - pa, b, n, k - pa); else if (a[pa - 1] > b[pb - 1]) return findKth(a, m, b + pb, n - pb, k - pb); else

        return a[pa - 1]; } class Solution { public: double findMedianSortedArrays(int A[], int m, int B[], int n) { int total = m + n; if (total & 0x1) return findKth(A, m, B, n, total / 2 + 1); else

            return (findKth(A, m, B, n, total / 2) + findKth(A, m, B, n, total / 2 + 1)) / 2; } };