Question #9072

write using c.In a disordered array of k(m) is the matching items from each group of identical items will leave only one remaining, and removing pursing an array to the beginning

Expert's answer

int findKthSmallest(int A[], int m, int B[], int n, int k) {

& assert(m >= 0); assert(n >= 0); assert(k > 0); assert(k <= m+n);

& int i = (int)((double)m / (m+n) * (k-1));

& int j = (k-1) - i;

& assert(i >= 0); assert(j >= 0); assert(i <= m); assert(j <= n);

& // invariant: i + j = k-1

& // Note: A[-1] = -INF and A[m] = +INF to maintain invariant

& int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);

& int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);

& int Ai = ((i == m) ? INT_MAX : A[i]);

& int Bj = ((j == n) ? INT_MAX : B[j]);

& if (Bj_1 < Ai && Ai < Bj)

return Ai;

& else if (Ai_1 < Bj && Bj < Ai)

return Bj;

& assert((Ai > Bj && Ai_1 > Bj) ||

(Ai < Bj && Ai < Bj_1));

& // if none of the cases above, then it is either:

& if (Ai < Bj)

// exclude Ai and below portion

// exclude Bj and above portion

return findKthSmallest(A+i+1, m-i-1, B, j, k-i-1);

& else /* Bj < Ai */

// exclude Ai and above portion

// exclude Bj and below portion

return findKthSmallest(A, i, B+j+1, n-j-1, k-j-1);

}

& assert(m >= 0); assert(n >= 0); assert(k > 0); assert(k <= m+n);

& int i = (int)((double)m / (m+n) * (k-1));

& int j = (k-1) - i;

& assert(i >= 0); assert(j >= 0); assert(i <= m); assert(j <= n);

& // invariant: i + j = k-1

& // Note: A[-1] = -INF and A[m] = +INF to maintain invariant

& int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);

& int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);

& int Ai = ((i == m) ? INT_MAX : A[i]);

& int Bj = ((j == n) ? INT_MAX : B[j]);

& if (Bj_1 < Ai && Ai < Bj)

return Ai;

& else if (Ai_1 < Bj && Bj < Ai)

return Bj;

& assert((Ai > Bj && Ai_1 > Bj) ||

(Ai < Bj && Ai < Bj_1));

& // if none of the cases above, then it is either:

& if (Ai < Bj)

// exclude Ai and below portion

// exclude Bj and above portion

return findKthSmallest(A+i+1, m-i-1, B, j, k-i-1);

& else /* Bj < Ai */

// exclude Ai and above portion

// exclude Bj and below portion

return findKthSmallest(A, i, B+j+1, n-j-1, k-j-1);

}

## Comments

## Leave a comment