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)