[TOC]

P004 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)).

思路分析

最简单的做法就是将两个数组先合并,再找中间位置

• 先循环一次将两个数组合并
• 检测是不是有没合并的遗漏的元素，遗漏的是最大的，放到最后
• 取新数组的中间位置

代码

java

public class Solution004 {

    private double getMedian(int a[]) {
        if ((a.length & 1) == 1)// 奇数
            return a[a.length / 2];
        else
            return 1.0 * (a[a.length / 2] + a[a.length / 2 - 1]) / 2.0;
    }

    public double findMedianSortedArrays(int A[], int B[]) {
        if (A.length == 0)
            return getMedian(B);
        if (B.length == 0)
            return getMedian(A);

        int arr[] = new int[A.length + B.length];
        int i = 0;
        int j = 0;
        int k = 0;

        // 合并
        while (k < arr.length && i < A.length && j < B.length) {
            if (A[i] <= B[j] && i < A.length)
                arr[k++] = A[i++];
            else
                arr[k++] = B[j++];
        }

        // 处理剩余
        while (i < A.length) {
            arr[k++] = A[i++];
        }

        // 处理剩余
        while (j < B.length) {
            arr[k++] = B[j++];
        }

        return getMedian(arr);
    }
}

python

class Solution004(object):
    def getMedian(self, arr):
        l = len(arr)
        if ((l & 1) == 1):
            return arr[l / 2]
        else:
            return 1.0 * (arr[l / 2] + arr[l / 2 - 1]) / 2.0
        
        
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        
        if len(nums1) == 0:return self.getMedian(nums2)
        if len(nums2) == 0:return self.getMedian(nums1)
        
        k = j = i = 0;
        l1 = len(nums1);l2 = len(nums2)
        total = l1 + l2
        arr = [0] * total;
        
        while(k < total and i < l1 and j < l2):
            if nums1[i] < nums2[j]:
                arr[k] = nums1[i]
                i += 1
            else:
                arr[k] = nums2[j]
                j += 1
            k += 1
        
        while i < l1:
            arr[k] = nums1[i]
            i += 1
            k += 1
             
             
        while j < l2:
            arr[k] = nums2[j]
            j += 1
            k += 1
        
        return self.getMedian(arr)