归并排序思想求两个有序数组的中位数

内容简介：归并排序思想求两个有序数组的中位数

原题

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

题目分析

这道题目在Leetcode上属于难度hard级别。

此题的基本思想可以借鉴归并排序。

第一步，先对两个有序列归并排序，不同的是当进行到一半时，便可终止归并，得到 i

$i$ 和 j $j$ 分别指向两个有序数组此时的位置。

第二步，如果两个数组的 总个数为奇数 ，则返回 i

$i$ 和 j $j$ 所指向的元素的更大者即可；

若为偶数，需要利用 i

$i$ 和 j $j$ 所指向的元素大小进行讨论。

• 若 i $i$ 所指向的元素更大，则循环中最后的遍历落在了 n u m s 1 $nums1$ 中，那么，如果 i − 1 > = 0 $i-1>=0$ （即 i $i$ 前存在前一个元素）且 n u m s 1 [ i − 1 ] > = n u m s 2 [ j ] $nums1[i-1] >= nums2[j]$ ，则中位数为 ( n u m s 1 [ i − 1 ] + n u m s 1 [ i ] ) / 2.0 $(nums1[i-1]+nums1[i])/2.0$ ；
• 如果 i − 1 = = 0 $i-1==0$ 或者 n u m s 1 [ i − 1 ] < n u m s 2 [ j ] $nums1[i-1] < nums2[j]$ ，则中位数为 ( n u m s 1 [ i ] + n u m s 2 [ j ] ) / 2.0 $(nums1[i] + nums2[j])/2.0$ ；若落在了 n u m s 2 $nums2$ 中，则对称地进行讨论。

需要注意的是边界情况，例如 n u m s 1 = 1 , n u m s 2 = k o n

$nums1={1}, nums2={ kong}$ 。

代码实现

public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
            int n1 = nums1.Length, n2 = nums2.Length, i = 0, j = 0;

            // sorting nums1 and nums2, sum pointer
            int sumpointer = 0; 
            for (i = 0, j = 0; (i < n1 || j < n2) && sumpointer <= (n1 + n2) >> 1; sumpointer++){
            //indicates nums1.Length<nums2.Length          
                if (i >= n1) j++;     
                //nums1.Length>nums2.Length                        
                else if (j >= n2) i++;
                //combination nums1 and nums2 to sort
                else if (nums1[i] <= nums2[j]) i++; 
                else j++;
            }

            bool even = (n1 + n2) % 2 == 0;
            --i; --j;
            if (i < 0) return even == true ? (nums2[j - 1] + nums2[j]) / 2.0 : nums2[j];
            if (j < 0) return even == true ? (nums1[i - 1] + nums1[i]) / 2.0 : nums1[i];

            //odd analysis
            if (!even) return Math.Max(nums1[i], nums2[j]);

            //even analysis
            //shows stone point is in nums2
            if (nums1[i] < nums2[j]){ 
                if (j - 1 >= 0 && nums1[i] <= nums2[j - 1])
                    return (nums2[j - 1] + nums2[j]) / 2.0;
                return (nums1[i] + nums2[j]) / 2.0;
            }
            // shows stone point is in nums1
            if (i - 1 >= 0 && nums2[j] <= nums1[i - 1])
                return (nums1[i - 1] + nums1[i]) / 2.0;
            return (nums1[i] + nums2[j]) / 2.0;

    }

结果分析：
时间复杂度为 O ( 0.5 ( m + n ) )

$O(0.5(m+n) )$ ，空间复杂度为 O ( 1 ) $O(1)$ ，计算结果排名：

以下是我之前写的一篇归并排序博客，地址，在此一块汇总到这里。
http://blog.csdn.net/daigualu/article/details/68491601

归并排序

归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（ Divide and Conquer ）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。

排序过程

归并排序的算法我们通常用递归实现，先把待排序区间 [start,end] 以中点二分，接着把左边子区间排序，再把右边子区间排序，这是分解的过程。最后把左区间和右区间用一次归并操作合并成有序的区间 [start,end] ，这是治理的过程。如何归并呢？ 简单来说两个指针分别指向待归并的数组，选出较小的，放到第三个指针控制的临时数组中。

实现代码

主题框架代码如下，见代码注释。

 /// <summary>
        /// 主题框架
        /// </summary>
        private void divideMerge(int[] unsort, int start, int end, int[] sort)
        {
            if (start < end)
            {
                int middle = (start + end) >> 1;
                //对前半部分归并排序
                divideMerge(unsort, start, middle, sort); 
                //对后半部分归并排序
                divideMerge(unsort, middle + 1, end, sort); 
                //此时，前、后半部分已经是有序序列，对它们实行二路归并
                merge(unsort, start, middle, end, sort);
            }

        }

调用的二路归并方法merge的实现代码如下，要特别注意临界值，此处pe为最大索引值，而不是元素个数，注意此处。

/// <summary>
        /// 合并算法
        /// </summary>
        /// <param name="unsort">无序数组</param>
        /// <param name="ps">第1部分的起始位置</param>
        /// <param name="pm">第1部分的结束位置</param>
        /// <param name="pe">第2部分的结束位置</param>
        /// <param name="sort"></param>
        private void merge(int[] unsort, int ps, int pm, int pe, int[] sort)
        {
            int i = ps; //第一部分的取值范围为[ps,pm]
            int j = pm+1; //第二部分的取值范围为[pm+1,pe]

            int sortCount = 0;

            while (i <= pm && j <= pe)
            {
                if (unsort[i] < unsort[j])
                    sort[sortCount++] = unsort[i++];
                else
                    sort[sortCount++] = unsort[j++];
            }

            while (i <= pm)
                sort[sortCount++] = unsort[i++];

            while (j <= pe)
                sort[sortCount++] = unsort[j++];

            for (int sortIndex = 0; sortIndex < sortCount; sortIndex++)
                unsort[ps + sortIndex] = sort[sortIndex];

        }

封装了一个排序类，见下，提供的API有2个，

1. 归并排序接口MergeSort()
2. 构造函数，构造无序数组

public class CMergeSort
    {
        private int[] _unsortArray;

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="unsortArray"></param>
        public CMergeSort(int[] unsortArray)
        {
            _unsortArray = unsortArray;
        }

        /// <summary>
        /// 归并排序接口
        /// </summary>
        /// <returns></returns>
        public int[] MergeSort()
        {
            int maxIndex = _unsortArray.GetUpperBound(0);
            int[] sort = new int[maxIndex + 1];
            divideMerge(_unsortArray, 0, maxIndex, sort);
            return sort;
        }
  }

客户端调用

客户端调用刚才写好的对象，对无序数组a实行归并排序。

static void Main(string[] args)
        {
            int[] a = new int[] { 9,7,10,6,3,5,2,7,9};
            var merge = new CMergeSort(a);
            int[] sortArray = merge.MergeSort();

            Console.Read();
        }

记录了归并排序的过程，对此进行了结果分析。

结果分析

对数组的 { 9,7,10,6,3,5,2,7,9} 的归并排序过程如下，

归并排序过程的前半部分，过程示意图见下，从图中可见，步骤 1 ， 2 ， 3 ， 4 一直分割区间，等到步骤 5 时，左右区间长度都为1，此时发生一次归并，结果再与另一个区间长度为1的归并，即步骤 6 ；步骤 7 分割，步骤 8 归并，步骤 9 归并后前半部分合并结束；
后半部分过程与前半部分归并一致，不再详述。

源码下载

http://download.csdn.net/detail/daigualu/9799598

我做Leetcode的专栏

http://blog.csdn.net/column/details/14761.html

汇总在GitHub上

地址，欢迎一起讨论！若有问题请联系我！
https://github.com/jackzhenguo/leetcode-csharp

以上所述就是小编给大家介绍的《归并排序思想求两个有序数组的中位数》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！

查看所有标签

猜你喜欢:

• Leetcode-计算两个排序数组的中位数
• php算法题：寻找有序数组的中位数
• 『算法导论』第 9 章：中位数与顺序统计量
• LeetCode4.寻找两个有序数组的中位数 JavaScript
• MergeSort归并排序和利用归并排序计算出数组中的逆序对
• 归并排序求逆序数

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。