Algorithm

OJ address

Leetcode website : 4. Median of Two Sorted Arrays

Description

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.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution in C

第一种解法：

#include <stdio.h>
int a[5000];

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int index1 = 0;
    int index2 = 0;
    int index3 = 0;
    while(index1<nums1Size && index2<nums2Size) {
        if (nums1[index1]<nums2[index2]) {
            a[index3++] = nums1[index1++];
        }
        else {
            a[index3++] = nums2[index2++];
        }
    }
    while (index1<nums1Size) {
        a[index3++] = nums1[index1++];
    }
    while (index2<nums2Size) {
        a[index3++] = nums2[index2++];
    }
    if ((index3 % 2) != 0) {
        return a[(index3-1)/2];
    }
    else {
        return (a[index3/2]+a[index3/2-1])/2.0;
    }   
}

int main(int argc, char const *argv[])
{
    int c[2] = {1,3};
    int b[2] = {2};
    double dd = findMedianSortedArrays(c,2,b,1);
    printf("dd:%g\n", dd);
    return 0;
}

第二种解法：

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int index1, index2, index3, index5, index6, res, resA, resB;
    index1 = index2 = index3 = index5 = index6 = res = resA = resB = 0;
    int length = nums1Size + nums2Size;
    if (length%2!=0) {
        index5 = (length-1)/2;
        index6 = 0;
    }
    else {
        index5 = res = length/2;
        index6 = length/2-1;
    }
    for (int i=0;i<length;++i) {
        if (index1<nums1Size && index2<nums2Size) {
            if (nums1[index1] < nums2[index2]) res = nums1[index1++];
            else res = nums2[index2++];
        }
        else if (index1<nums1Size) res = nums1[index1++];
        else res = nums2[index2++];
        if (i == index5) resA = res;
        if (i == index6) resB = res;
    }
    return (length%2!=0) ? resA : ((resA + resB)/2.0);
}

Solution in Python

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        i = 0
        j = 0
        length = len(nums1)+len(nums2)
        if length%2!=0:
            res = (length-1)/2
            respre = 0
        else:
            res = length/2
            respre = length/2-1
        for x in range(length):
            if i < len(nums1) and j < len(nums2):
                if nums1[i] < nums2[j]:
                    dd = nums1[i]
                    i = i+1
                else:
                    dd = nums2[j]
                    j = j+1
            elif i < len(nums1):
                dd = nums1[i]
                i = i+1
            elif j < len(nums2):
                dd = nums2[j]
                j = j+1
            if x == res:
                resA = dd
                break
            if x == respre:
                resB = dd
        if length%2!=0: 
            return resA   
        else: 
            return (resA + resB)/2.0
        
if __name__ == '__main__':
    a = Solution()
    d1 = [1,2]
    d2 = [3]
    c = a.findMedianSortedArrays(d1,d2)
    print c

My Idea

题目含义是，给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

关于复杂度的理解就是，不要用排序去做，一次遍历解决这道题目，其实不用一遍遍历也可以解决这个题目，我写了两个解法:

1. 第一种解法就是全部遍历，在遍历的时候比较两个数组每各元素的大小，将最小的元素存到新的数组中，然后遍历结束，在新的数组中找到中位数即可。算法的时间复杂度是O（m+n）
2. 显然第一种解法是全部遍历，但是还有更好的方法，就是不用开数组，仅仅比较给到的两个数组，由于给到的数组长度是题目给你的，那中位数的位置也是固定的了，其实就是比较两个数组，一直比较到中位数的那个位置，然后保存中位数，直接返回结果就可以了。中位数的位置就是两个数组中间的位置。所以时间复杂度是O（(m+n)/2）,比第一种方法快一倍。而且不用开数组保存，大大的节约了空间复杂度。只要开变量保存结果就可以了。