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)
