力扣算法题——寻找两个有序数组的中位数练习

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

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

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

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0


示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays
-----------------------------------------------------------分割线---------------------------------------------------------------

看到这道题,首先想到的是中位数的计算公式,当数组长度是偶数时,将数组按大小排列,取中间两个数组的平均数;当数组长度是奇数时,中位数是按大小排列后数组最中间的数值。

了解完计算方法之后,这道题就有了大致的思路:

1、合并两个数组

2、对新数组进行排序

3、根据公式计算中位数

开始写的时候,数组排序算法自己随便写了个冒泡排序,但运行的后发现代码效率比较低下,后来想起来列表里自带有一个sort()方法可以实现排序,所以后面改成这个方式,执行速度提高了不少,代码如下:

 public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
         double _result = 0.0d;
            int _max = Math.Max(nums1.Length, nums2.Length);
            List _numList = new List(nums1.Concat(nums2));//合并数组
                                                                    //排序
            _numList.Sort();
            //计算中位数
            if (_numList.Count % 2 == 0)
            {
                int _middle = _numList.Count / 2;
                _result = Math.Round(((double)(_numList[_middle - 1] + _numList[_middle]) / 2),1);
            }
            else
            {
                int _middle = (_numList.Count+1) / 2;
                _result = Math.Round((double)_numList[_middle-1],1);
            }


            return _result;
    }

力扣算法题——寻找两个有序数组的中位数练习_第1张图片

 

 

你可能感兴趣的