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++]);elselist.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;elsereturn 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));elsereturn 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)/2int 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)