当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.004.Median of Two Sorted Arrays

LeetCode.004.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

解题过程

求两个有序数组的中位数,很经典的题,貌似面试时也被问过,但没自己解决过。

O(m+n)归并排序法

我只会简单的归并排序法,写了一版,通过了,速度还不慢,打败了93%:

//归并排序法
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int[] res = new int[nums1.length+nums2.length];
    int i=0,j=0,k=0;
    while(i<nums1.length && j<nums2.length){
        if(nums1[i] <= nums2[j])
            res[k++] = nums1[i++];
        else
            res[k++] = nums2[j++];
    }
    while(i < nums1.length)
        res[k++] = nums1[i++];
    while(j < nums2.length)
        res[k++] = nums2[j++];
    return res.length%2==0 ? (double)(res[res.length/2]+res[(res.length/2)-1])/2 : res[res.length/2];
}

O(log(m+n))分治法

要是面试的话,这时候肯定要问怎么优化了,看到复杂度要求为O(log(m+n)),能想到肯定用二分、二叉来解决,不会做。看了看Solution,又上网搜,能搜到好多文章,这道题扩展下还能引出适用性更广的求两个有序数组的第k个元素
其实我感觉就用归并挺好的,写着简单,效率也不差,当然O(log(m+n))的分治法思想也要知道。


GitHub代码


上一篇 LeetCode.014.Longest Common Prefix

下一篇 LeetCode.009.Palindrome Number

阅读
458
阅读预计2分钟
创建日期 2018-02-07
修改日期 2018-02-07
类别
百度推荐