LeetCode 4. Median of Two Sorted Arrays 两个排序数组的中位数

题目

https://leetcode.com/problems/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)).

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

讲解

对于一个长度为n的已排序数列,若n为奇数,中位数为第n / 2 + 1位置的数字。 若n为偶数,则中位数为(第n / 2 位置的数字 +第n / 2 + 1位置的数字) / 2。

因此如果我们把问题转化为找出在两个数列中第K小的元素,就可以找到中位数。

取A[k / 2] B[k / 2] 比较; 如果 A[k / 2] > B[k / 2] ,所求的元素必然不在B的前k / 2个元素中; 反之,必然不在A的前k / 2个元素中,于是我们可以将A或B数列的前k / 2元素删去,在剩下两个数列中查找第k个数。

如果k == 1,则比较A或B中第一个数字,较小的为第k个数字。

如果A或者B其中一个数列为空,则只用在另一个数列中找第k个数字。

视频教学

Java参考代码

public class Solution { 
    public double findMedianSortedArrays(int[] nums1, int[] nums2) { 
        int len = nums1.length + nums2.length; 
        if (len % 2 == 1) { 
            return findKth(nums1, 0, nums2, 0, len / 2 + 1); 
        } else { 
            return (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0; 
        } 
    } 
     
    public int findKth(int[] A, int startA, int[] B, int startB, int k) { 
        if (startA >= A.length) { 
            return B[startB + k - 1]; 
        } 
         
        if (startB >= B.length) { 
            return A[startA + k - 1]; 
        } 
         
        if (k == 1) { 
            return Math.min(A[startA], B[startB]); 
        } 
         
        int indexA = startA + k / 2 - 1; 
        int indexB = startB + k / 2 - 1; 
        int keyA = indexA < A.length ? A[indexA] : Integer.MAX_VALUE; 
        int keyB = indexB < B.length ? B[indexB] : Integer.MAX_VALUE; 
         
        if (keyA < keyB) { 
            return findKth(A, startA + k / 2, B, startB, k - k / 2); 
        } else { 
            return findKth(A, startA, B, startB + k / 2, k - k / 2); 
        } 
    } 
} 

发表评论

电子邮件地址不会被公开。 必填项已用*标注