Leetcode算法系列| 4. 寻找两个正序数组的中位数

1.题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

• 示例1:

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

• 示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

• 提示：
  • nums1.length == m
  • snums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums1[i], nums2[i] <= 10^6

2.题解

C# 解法一：合并List根据长度找中位数

• 提new 一个 List , 并将 nums1 和 nums2 都添加到list 中，然后进行排序。对于排序后的 list, 根据长度计算出中位数的index，进而计算出最终结果。假设合并后的list长度为13，则从小到大第7个数字为中位数，resultIndex=6;假设合并后的list长度为14，则从小到大第7，8个数字的平均值为中位数，index 分别为 6，7，此时resultIndex =7,resultIndex-1 =6 , 结果为 ( list[resultIndex-1] + list[resultIndex] ) / 2.0 ;

public class Solution {
     public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        int m = nums1.Length;
        int n = nums2.Length;
        int len = m + n;
        var resultIndex = len / 2;
        List<int> list = new List<int>(nums1);
        list.AddRange(nums2);
        list.Sort();
        if (len % 2 == 0)
        {
            return (list[resultIndex - 1] + list[resultIndex]) / 2.0;
        }
        else
        {
            return list[resultIndex];
        }
    }
}

• 时间复杂度：O( (m+n)(1+log(m+n) ))
  • 将长度为m,n的两个数组添加到list，复杂度分别为常数级的m和n ；list.Sort()的复杂度根据官方文档可得为 (m+n)log(m+n)，所以该方法时间复杂度为 O( m+n+(m+n)log(m+n) ) = O( (m+n)(1+log(m+n) ))
• 空间复杂度：O(m+n)
  • 使用list的长度为m+n.

C# 解法二：归并排序后根据长度找中位数

• 方法一使用了list.Sort() 方法，可以对list进行排序，但是，若题目给出的nums1 和 nums2 是无序数组，使用 list.Sort() 才算是 物有所用。 本题中 nums1 和 nums2 是有序数组，所以使用 list.Sort() 有写 杀鸡用宰牛刀的感觉，换句话说，这里面存在着效率的浪费。我们可以利用 【nums1 和 nums2 是有序数组】 这个条件，来精简我们的排序。

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        // nums1 与 nums2 有序添加到list中
        List<int> list = new List<int>();
        int i = 0, j = 0;
        int m = nums1.Length;
        int n = nums2.Length;
        int len = m + n;
        var resultIndex = len / 2;

        while (i < m && j < n)
        {
            if (nums1[i] < nums2[j])
                list.Add(nums1[i++]);
            else
                list.Add(nums2[j++]);
        }
        while (i < m) list.Add(nums1[i++]);
        while (j < n) list.Add(nums2[j++]);

        if (len % 2 == 0)
        {
            return (list[resultIndex - 1] + list[resultIndex]) / 2.0;
        }
        else
        {
            return list[resultIndex];
        }
    }
}

• 时间复杂度：O(m+n)
  • i 和 j 一起把长度为 m 和 n 的两个数组遍历了一遍，所以时间复杂度为 O(m+n)
• 空间复杂度：O(m+n)
  • 使用list的长度为m+n.

C# 解法三：方法二的优化，不真实添加到list

• 对于方法二，我们在已知 resultIndex 的情况下，也可以不把 nums1 和 nums2 真实添加到 list 中，只需要在i 和 j 不断向右移动的过程中，计算是否到达了 resultIndex 即可。 若到达了 resultIndex，可以直接返回结果，而不必再处理后面的数据。但是相对的，我们需要在 i 或者 j 向右移动时，判断是否到达了resultIndex.

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        int i = 0, j = 0, m = nums1.Length, n = nums2.Length;
        int len = m + n;
        int resultIndex = len / 2;
        int resultIndexPre = resultIndex - 1;
        int result = 0, resultPre = 0;  
        bool isTwoResult = len % 2 == 0;
        while (i < m || j < n)
        {
            var nums1ii = i < m ? nums1[i] : int.MaxValue;
            var nums2jj = j < n ? nums2[j] : int.MaxValue;
            if (nums1ii < nums2jj)
            {
                if (i + j == resultIndexPre) resultPre = nums1[i];
                if (i + j == resultIndex)
                {
                    result = nums1[i];
                    if (isTwoResult) return (resultPre + result) / 2.0;
                    else return result;
                }
                i++;
            }
            else
            {
                if (i + j == resultIndexPre) resultPre = nums2[j];
                if (i + j == resultIndex)
                {
                    result = nums2[j];
                    if (isTwoResult) return (resultPre + result) / 2.0;
                    else return result;
                }
                j++;
            }
        }
        return 0;
    }
}

• 时间复杂度：O(m+n)
  • i 和 j 一起把长度为 m 和 n 的两个数组遍历了一半，但是每一步都需要判断当前i+j的值是否等于resultIndex，所以时间复杂度仍可认为 O(m+n)
• 空间复杂度：O(1)
  • 对比方法二，不再使用list，只使用了几个变量来存值，所以空间复杂度为O(1)

C# 解法四：第k小数

• 前面的几种方法，时间复杂度都没有达到题目要求的 O(log(m+n)) 。 看到log，很明显需要使用二分法。根据 windliang提供的思路，题目求中位数，实际上是求第 k 小数的一种特殊情况，而求第 k 小数 有一种算法。

方法三中，i 和 j 每次向右移动一位时，相当于去掉了一个不可能是中位数的值，也就是一个一个的排除。由于给定的两个数组是有序的，所以我们完全可以一半一半的排除。假设我们要找第 k 小数，我们每次循环可以安全的排除掉 k/2 个数。

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        int n = nums1.Length;
        int m = nums2.Length;
        int len = n + m;
        int kPre = (len + 1) / 2;
        int k = (len + 2) / 2;
        if (len % 2 == 0)
            return (GetKth(nums1, 0, n - 1, nums2, 0, m - 1, kPre) + GetKth(nums1, 0, n - 1, nums2, 0, m - 1, k)) * 0.5;
        else
            return GetKth(nums1, 0, n - 1, nums2, 0, m - 1, k);
    }

    private int GetKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k)
    {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
        if (len1 > len2) return GetKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];
        if (k == 1) return Math.Min(nums1[start1], nums2[start2]);
        int i = start1 + Math.Min(len1, k / 2) - 1;
        int j = start2 + Math.Min(len2, k / 2) - 1;
        if (nums1[i] > nums2[j])
            return GetKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        else
            return GetKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
    }
}

• 时间复杂度：O(log(m+n))
  • i每进行依次循环，就减少 k/2个元素，所以时间复杂度为 O(log(k)) , 而 k = (m+n)/2 , 所以最终复杂度是 O(log(m+n))
• 空间复杂度：O(1)
  • 只使用了几个变量来存值，递归是尾递归不占用堆栈, 所以空间复杂度为O(1)

C# 解法五：从中位数的概念定义入手

• 该方法参考了 LeetCode 题解的 官方题解 以及 windliang 的题解。
  首先我们来看一下百度百科中位数的定义：https://baike.baidu.com/item/%E4%B8%AD%E4%BD%8D%E6%95%B0/3087401?fr=aladdin

public class Solution {
  public double FindMedianSortedArrays(int[] A, int[] B)
    {
        int m = A.Length;
        int n = B.Length;
        //保证第一个数组是较短的
        if (m > n) return FindMedianSortedArrays(B, A);
        //正在寻找的范围为 [ A[iMin],A[iMax] ) , 左闭右开。二分查找取i=(iMin+iMax)/2
        int iMin = 0, iMax = m;
        while (iMin <= iMax)
        {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;
            if (j != 0 && i != m && B[j - 1] > A[i])
            { // i 需要增大
                iMin = i + 1;
            }
            else if (i != 0 && j != n && A[i - 1] > B[j])
            { // i 需要减小
                iMax = i - 1;
            }
            else
            { // 达到要求，并且将边界条件列出来单独考虑
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j - 1]; }
                else if (j == 0) { maxLeft = A[i - 1]; }
                else { maxLeft = Math.Max(A[i - 1], B[j - 1]); }
                if ((m + n) % 2 == 1) { return maxLeft; } // 奇数的话不需要考虑右半部分

                int minRight = 0;
                if (i == m) { minRight = B[j]; }
                else if (j == n) { minRight = A[i]; }
                else { minRight = Math.Min(B[j], A[i]); }

                return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果
            }
        }
        return 0.0;
    }
}

• 时间复杂度：O(log(min(m，n))
  • 我们对较短的数组进行了二分查找，所以时间复杂度是 O(log(min(m，n))
• 空间复杂度：O(1)
  • 只使用了几个变量来存值，所以空间复杂度为O(1)