codility上の問題(14)Nu 2011

この問題の記述は面倒ではなく,2つの秩序化された整数配列A,Bの長さはそれぞれM,N,さらに4つの長さKの配列P,Q,R,Sを与えた.0<=P[i]<=Q[i]< M, 0<=R[i]<=S[i]< N
A中子配列[P[i],Q[i]]を切り出し,B中子配列[R[i],S[i]]を切り出し,一つの配列を形成する中位数は全部でK個あり,このK個数の中位数を求める.
データ範囲N,M[1.10^5]
K [1..10^4]
要求複雑度時間O(K*(log(N)+log(M)),空間O(k)
Kが奇数であることを容易に保証するために、Q[i]-P[i]+1+S[i]-Q[i]+1は奇数である.
分析:
この問題はkサブ配列に対して,それぞれ中位数を求めればよいが,これは2つの秩序配列のk番目の要素のアルゴリズムを用いた.それはlog(M)+log(N)時間で解決できる.
具体的なアルゴリズム:
a配列にnuma個の要素があり,b配列にumb個の要素があると仮定する.1つが空の場合は、別の配列の対応する要素を直接返します.
k=1またはk=numa+numbの場合、最小および最大の要素がそれぞれ返されます.
そうでなければkをka,kbの2つの部分に分け,ka+kb=k
集計プロセスを想定して
a[ka−1]<=b[kb−1]の場合,a[ka−1]を先に集計し,b[kb−1]を集計することを考慮した.a[ka−1]を集計した後、集計の合計個数はka+kb=kより小さいため、a[0..ka−1]種はk番目に小さい元素を含まない.同様に、b[kb−1]を再集計した後、我々が集計した元素数はka+kb=k以上であるに違いないので、b[kb..N−1]もk番目の元素を含まないに違いない.だからaの前半とbの後半は捨てることができます.a[ka−1]>b[kb−1]の場合、状況は対称である.
つまり、小さな要素の配列の前の部分(自分を含む)と、大きな要素の配列の後ろの部分(自分を含まない)を毎回捨てることができます.
この問題が解決した後,長さCの配列を得,直接並べ替えて中位数を求めることも,スナップパーティションのような方法で線形時間でその中の位数を求めることもできる.
早送りにすると最後の総複雑度はO(k*(log(M)+log(N)+log(K))であり、早送りにしないのはO(K*(log(M)+log(N))であるはずである.
コード:
 

int give(int *a,int *b,int numa,int numb,int k) {
    if (numa == 0) {
        return b[k - 1];
    }
    if (numb == 0) {
        return a[k - 1];
    }
    if (k == 1) {
        return (a[0] < b[0])?a[0]:b[0];
    }
    if (k == numa + numb) {
        return (a[numa - 1] > b[numb - 1])?a[numa - 1]:b[numb - 1];
    }
    int ka = k * 1. * numa / (numa + numb);
    if (ka == 0) {
        ka = 1;
    }
    int kb = k - ka;
    if (kb > numb) {
        kb = numb;
        ka = k - kb;
    }
    return (a[ka - 1] <= b[kb - 1])?give(a + ka, b, numa - ka, kb, k - ka):give(a, b + kb, ka, numb - kb, k - kb);
}
        

int findk(int *a,int n,int k) {
int i,j,t;
 
    for (i = 1, j = n - 1;; ++i,--j) {
        for (; (i <= j) && (a[i] < a[0]); ++i)   //i <= j      (i < n)
        ;
        for (; (j >= i) && (a[j] > a[0]); --j)    // j >= i      (j > 0)
        ;
            
        if (i >= j) {
            break;
        }
      	t = a[i];
        a[i] = a[j];
        a[j] = t;
       
    }
    t = a[0];
    a[0] = a[j];
    a[j] = t;
    if (j == k - 1) {
        return a[j];
    }
    if (j > k - 1) {
        return findk(a, j , k);
    }
    else {
        return findk(a + j + 1, n - j - 1, k - j - 1);
    }
    
}
int c[10002];
    
int solution(int A[], int N, int B[], int M, int P[], int Q[], int R[], int S[], int K) {
    // write your code here...
int i;
    for (i = 0; i < K; ++i) {
        c[i] = give(A + P[i], B + R[i], Q[i] - P[i] + 1, S[i] - R[i] + 1, (Q[i] - P[i] + 1 + S[i] - R[i] + 1) / 2 + 1);
    }
    return findk(c, K , K / 2 + 1);
 
}