LeetCode #4 Median of Two Sorted

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Follow up: The overall run time complexity should be O(log (m+n)).

 

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000
Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000
Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000
 

Constraints:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

ABSTRACT: By definition, if we were to combine the two input arrays into one array,
the median would be:

1. the (m + n) / 2 -th element when m + n is odd and
2. the avg of (m + n) / 2 - 1 -th and (m + n) / 2 -th elements when m + n is even;
   here the indices start from 0.
   Listed below are three different solutions(or put more precisely, two different
   solutions since the last two are just different implementations of the same idea),
   the first one of which does not take advantage of the fact that the two input arrays
   are sorted, thus it works in situations where the input arrays are in radom order
   while the two impls that follow rely on the input arrays being sorted.

The last impl differs very slightly from the second one(see their return statements)
but the improvement gained has been surprisingly great; the take-away here is this:
prefer ptr comparison over integer arithmetics whenever possible, especially when
multiplication, division or modular op are involved.

/*
60ms
*/
void exch(int *s, int i, int j) {
    int t = *(s + i);
    *(s + i) = *(s + j);
    *(s + j) = t;
}

int partition(int a[], int lo, int hi) {
    if (lo == hi) { return lo; }
    int i = lo, j = hi + 1, v = a[lo];
    while (1) {
        while (a[++i] < v) if (i == hi) break;
        while (a[--j] > v) if (j == lo) break;
        if (i >= j) break;
        exch(a, i, j);
    }
    exch(a, lo, j);
    return j;
}

int kth(int a[], int n, int k) {
    int p = -1, lo = 0, hi = n - 1;
    while (1) {
        p = partition(a, lo, hi);
        if (p == k) {
            break;
        } else if (p < k) {
            lo = p + 1;
        } else {
            hi = p - 1;
        }
    }

    return a[p];
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int total = nums1Size + nums2Size;
    int *a = (int*)malloc(total * sizeof(*a));
    if (nums1Size > 0) { for (int i = 0; i < nums1Size; i++) { a[i] = nums1[i]; } }
    if (nums2Size > 0) { for (int i = 0; i < nums2Size; i++) { a[nums1Size + i] = nums2[i]; } }
    for (int i = 0; i < total; i++) { printf("%i%s", a[i], i == total - 1 ? "\n" : " "); }
    if (total % 2 == 0) {
        return (kth(a, total, total / 2) + kth(a, total, total / 2 - 1)) / 2.0f;
    } else {
        return kth(a, total, total / 2);
    }
}

/*
24ms
*/
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int *a = nums1, m = nums1Size, *b = nums2, n = nums2Size;

    int i = 0, j = 0, t = 0, t1 = 0, t2 = 0, *ptr = &t1;
    do {
        if (i == m) {
            *ptr = b[j++];
        } else if (j == n) {
            *ptr = a[i++];
        } else {
            if (a[i] < b[j]) {
                *ptr = a[i++];
            } else {
                *ptr = b[j++];
            }
        }
        t++;
        ptr = ptr == &t1 ? &t2 : &t1;
    } while (t <= (m + n) / 2);
    return (m + n) % 2 ? (t % 2 ? t1 : t2) : (t1 + t2) / 2.0f;
}

/*
8ms
*/
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int *a = nums1, m = nums1Size, *b = nums2, n = nums2Size;

    int i = 0, j = 0, t = 0, t1 = 0, t2 = 0, *ptr = &t1;
    do {
        if (i == m) {
            *ptr = b[j++];
        } else if (j == n) {
            *ptr = a[i++];
        } else {
            if (a[i] < b[j]) {
                *ptr = a[i++];
            } else {
                *ptr = b[j++];
            }
        }
        t++;
        ptr = ptr == &t1 ? &t2 : &t1;
    } while (t <= (m + n) / 2);
    return (m + n) % 2 ? (ptr == &t2 ? t1 : t2) : (t1 + t2) / 2.0f;
}