LeetCode #4 Median of Two Sorted

2020-12-14  本文已影响0人  刘煌旭
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;
}
上一篇 下一篇

猜你喜欢

热点阅读