C#LeetCode刷题之#4-两个排序数组的中位数(Median of Two Sorted Arrays)

C#LeetCode刷题之#4-两个排序数组的中位数(Median of Two Sorted Arrays)

问题

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n))

你可以假设 nums1 和 nums2 不同时为空。

nums1 = [1, 3]

nums2 = [2]

中位数是 2.0

nums1 = [1, 2]

nums2 = [3, 4]

中位数是 (2 + 3)/2 = 2.5

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

You may assume nums1 and nums2 cannot be both empty.

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

nums1 = [1, 2]

nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

中位数(又称中值,英语:Median),统计学中的专有名词,代表一个样本、种群或概率分布中的一个数值,其可将数值集合划分为相等的上下两部分。

对于有限的数集,可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个,通常取最中间的两个数值的平均数作为中位数。

这道题经过简单的思维转换其实可以转换成求第k小的值问题,首先合并2个数组,再找出第k小的值。该题需要根据原问题规模(m+n)的奇偶性做出相应调整。

示例

public class Program {

    public static void Main(string[] args) {
        int[] nums1 = { 1, 2, 3 };
        int[] nums2 = { 4, 5 };

        var res = FindMedianSortedArrays(nums1, nums2);

        Console.WriteLine($"The median is {res}.");

        Console.ReadKey();
    }

    private static double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int size = nums1.Length + nums2.Length;

        int[] union = new int[size];

        int mid = size / 2;
        int even = (size % 2 == 0) ? 1 : 0;

        int m1, m2;
        int left, right;

        for(int i = m1 = m2 = 0; i < size; i++) {
            left = m1 < nums1.Length ? nums1[m1] : int.MaxValue;
            right = m2 < nums2.Length ? nums2[m2] : int.MaxValue;

            if(left < right) {
                union[m1 + m2] = nums1[m1];
                m1++;
            } else {
                union[m1 + m2] = nums2[m2];
                m2++;
            }

            if(i == mid) break;
        }
        return (union[mid] + union[mid - even]) / 2.0;
    }

}

以上给出1种算法实现,以下是这个案例的输出结果:

The median is 3.

分析:

显然这种解法在最坏的情况下的时间复杂度为 O(m+n) ,并没有达到题中要求的 O(log (m+n)) ,这里仅为标记,稍后再来改进算法。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4005

发表评论

登录后才能评论