【LeetCode#4】Median of Two Sorted Arrays

一、描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.

有两个大小分别为m和n的排序数组nums1nums2

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

查找两个排序数组的中位数。总的运行时间复杂度应该是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

二、相关知识

中位数(Median):

中位数(又称值,英语:Median),统计学的专有名词,代表一个样本、种群或概率分布的一个数值,其可将数值集合划分为相等的上下两部分。 对于有限的集,可以通过把所有观察值高低排序后找出正中间的一个作为中位数。 如果观察值有偶数个,通常取最中间的两个数值的平均作为中位数

三、解决方案(Java)

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] nums3 = new int[m+n];
        int i=0,j=0;
        double median = 0;
        for(int k = 0;k<m+n;k++){
            if(i > m-1 && j < n){
                nums3[k] = nums2[j ++];
            }else if(j > n-1 && i<m){
                nums3[k] = nums1[i++];
            }else if(i<m && j<n){
                if(nums1[i]>nums2[j]){
                    nums3[k] = nums2[j++];
                }else{
                    nums3[k] = nums1[i++];
                }
            }
        }
        if((m+n)%2 == 0){
            median = (nums3[(m+n)/2] +nums3[(m+n)/2 -1] + 0.0)/2.0;
        }else{
            median = nums3[(m+n)/2];
        }
        return median;

    }
}
四、最后的最后

这是一种错误的解法。

0

发表评论

微信扫一扫,分享到朋友圈

【LeetCode#4】Median of Two Sorted Arrays
返回顶部