LeetCode 4

Median of Two Sorted Arrays

题目:

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.

描述：两个已经排序好的数组，数组不是空，求中位数。要求算法的时间复杂度是O(long(m+n))。

分析:

1、如果不看时间复杂度的话，可以使用暴力方法实现：把两个数组拼接，然后重新排序，寻找中位数，较为简单，使用Java实现。
2、要是考虑复杂度的话，较为困难，后面会用C语言具体分析。

1、Java实现

内容简单，这里不做解释。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        double median = 0.0f;
        int m = nums1.length;
        int n = nums2.length;
        int[] newNums = Arrays.copyOf(nums1, nums1.length + nums2.length);

        System.arraycopy(nums2, 0, newNums, nums1.length, nums2.length);
        Arrays.sort(newNums);

        if ((m + n) % 2 == 0) {
            median = (newNums[(m + n) / 2] + newNums[(m + n) / 2 - 1]) / 2.0;
        } else {
            median = newNums[(m + n) / 2];
        }

        return median;
    }

运行时间：

image.png

时间复杂度：主要是Arrays.sort()使用的快排，时间复杂度为O( (n+m)*log(n+m) )

空间复杂度：O(n+m)

2、 C语言实现(1)

新建一个长度为 (m+n)/2 +1 的数组newnums，i,j为先指向数组nums1 和mums2的第0个元素,通过i,j的移动把两个源数组的按照升序复制到新数组newnums中。

• 1. 处理源数组是空的情况，一个如果是空，另一个直接复制数组到newnums中。

• 2. 两个都不为空，开始循环，循环次数为length/2+1(总长度一半+1)

• 3. 控制移动边界i>=num1Size时，nums1到最后一个元素，从nums2赋值，j>=num2Size时，nums2到最后一个元素，从nums1赋值。
  判断nums1[i] < nums2[j],每次都把较小的元素赋值到新数组中。

• 4.分偶数和奇数判断中位数情况。

double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size) {

    int length = nums1Size + nums2Size;
    int *newnums = (int *) malloc(sizeof(int) * (length / 2 + 1));
    int index = 0, i = 0, j = 0;


    double median;
    if (nums1Size == 0) {
        newnums = nums2;
    } else if (nums2Size == 0) {
        newnums = nums1;
    } else {

        while (index <= length / 2) {

            if (i >= nums1Size) {
                newnums[index] = nums2[j];
                j++;
            } else if (j >= nums2Size) {
                newnums[index] = nums1[i];
                i++;
            } else {
                if (nums1[i] < nums2[j]) {
                    newnums[index] = nums1[i];
                    i++;
                } else {
                    newnums[index] = nums2[j];
                    j++;
                }
            }

            index++;
        }
    }

    if (length % 2 == 0) {
        median = (newnums[length / 2 - 1] + newnums[length / 2]) / 2.0;
    } else {
        median = newnums[length / 2];
    }
    return median;
}

运行时间：

image.png

时间复杂度：O((n+m)/2+1) = O(n)

空间复杂度：O((n+m)/2+1) = O(n)

3、C语言实现(2)

中位数的定义是把一个集合分为左右长度相等的两个子集合，所以我们如果保证两个数组的，左半部分的长度=右半边分长度，就可以找出中位数。
这时候要保证:

len(left_part) = len(right_part)
max(left_part) <=min(right_part)

令

len(left_part) = i
len(right_part)) = j
i = m - i
j = n - j

因此我们需要确保

• i + j = m - i +n - j (or i + j = m - i + n - j + 1)
  if m<=n 我们需要设置 i ~(0,m) ， j = (m + n + 1)/2 - i
• nums2[j−1]≤nums1[i] 和 nums1[i−1]≤nums2[j]

我们需要先确保m<=n，如果m>n时，j可能会小于 0，然后使用二分法查询数组，处理好四种边界问 题i = 0 ，j = 0 ，i = m 或 j = n的情况，具体细节看代码。

double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size) {

    int m = nums1Size;
    int n = nums2Size;

    if (m > n) { // to ensure m<=n
        int *temp = nums1;
        nums1 = nums2;
        nums2 = temp;

        int tmp = m;
        m = n;
        n = tmp;
    }

    int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;

    while (iMin <= iMax) {
        int i = (iMin + iMax) / 2;
        int j = halfLen - i;

        if (i < iMax && nums2[j - 1] > nums1[i]) {
            iMin = i + 1; // i is too small
        } else if (i > iMin && nums1[i - 1] > nums2[j]) {

            iMax = i - 1; // i is too big

        } else { // i is perfect

            int maxLeft = 0;

            if (i == 0) {
                maxLeft = nums2[j - 1];
            } else if (j == 0) {
                maxLeft = nums1[i - 1];
            } else {
                maxLeft = nums1[i - 1] > nums2[j - 1] ? nums1[i - 1] : nums2[j - 1];
            }

            if ((m + n) % 2 == 1) {
                return maxLeft;
            }

            int minRight = 0;

            if (i == m) {
                minRight = nums2[j];
            } else if (j == n) {
                minRight = nums1[i];
            } else {
                minRight = nums2[j] > nums1[i] ? nums1[i] : nums2[j];
            }

            return (maxLeft + minRight) / 2.0;
        }
    }
    return 0.0;
}

耗时如图：

image.png

还是比较不错的。
时间复杂度：O(log(min(m,n))).
空间复杂度：O(1)