背景
给定两个大小分别为 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
感兴趣的小伙伴可以查看原题： leetcode.cn/problems/me…网络异常，图片无法展示|
分析
根据题意，我们的目标是找到两个正序数组的中位数，比如[1,2,3]中位数是2，[1,2,3,4]中位数是(2+3)/2=2.5；
首先，我们的第一步就是合并两个正序数组；
再排序好的数组中，我们找到中间位置的数字；如果合并后的数组长度是偶数，那么需要找到中间位置的两个数字再计算出中位数；如果合并后的数组长度是奇数，那么直接找到中间位置的数字即可；
java实现
第一步：先计算两个正序数组的长度，计算长度有两个作用：
- 判断是否有数组为空，如果有数组为空，那么我们就不需要合并数组了，直接找出中位数；
- 如果没有数组为空，那么我们需要先创建一个合并数组来接收合并的结果，创建合并数组是需要用到总长度的。
第二步：计算中间位置。我们在创建合并数组时，可以只创建一个只有mid+1长度的数组，不需要把两个数组完全排序好，因为我们的目标是计算中位数。
第三步：合并数组；
- 需要准备好两个指针idx1，idx2分别指向数组1和数组2的起始位置;
- 逐步比较idx1位置和idx2位置的数值大小；如果idx1位置数值小，那么就把该数值放进合并数组中，同时idx1自增，idx2不动，合并数组的索引也自增；否则就反过来，idx2对应位置数值放进合并数组中，idx2自增，idx1不动，合并数组索引自增；
- 直至合并数组索引位到达mid位置停止；
第四步：计算中位数；如果两个数组总长度是偶数，那么需要拿出合并数组mid索引位和mid-1索引位的数值计算中位数；如果是奇数，那么直接拿出mid索引位的数值；
public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 计算nums1的数组长度 int len1 = nums1==null?0:nums1.length; // 计算nums2的数组长度 int len2 = nums2==null?0:nums2.length; // 计算总长度 int total = len1+len2; // 计算中间位置 int mid = total/2; // 如果两个数组都是空 if(len1==0&&len2==0){ return 0.0; } // 如果数组1为空 if(len1==0){ // 如果只有一位数 if(mid==0){ return nums2[mid]; } // 判断总长度是奇数还是偶数，偶数需要中间两位计算中位数，奇数直接返回中间位置数值 return total%2==0?(nums2[mid]+nums2[mid-1])/2.0:nums2[mid]; } // 如果数组2为空 if(len2==0){ // 如果只有一位数 if(mid==0){ return nums1[mid]; } // 判断总长度是奇数还是偶数，偶数需要中间两位计算中位数，奇数直接返回中间位置数值 return total%2==0?(nums1[mid]+nums1[mid-1])/2.0:nums1[mid]; } // 创建合并数组，只需要创建mid+1长度即可，不需要完全排序完毕 int[] megerArray = new int[mid+1]; // 创建两个指针指向数组1和数组2的起始位置 int idx1 = 0; int idx2 = 0; // 循环初始化合并数组，合并排序过程 for(int i=0;i<=mid;i++){ // 考虑到两个数组长度不一，所以需要Integer类型来判断是否从数组中取出值； // 如果是int类型的话，默认是0，那么不好判断该值是否是从数组中取出来的； Integer n1 = null; Integer n2 = null; // 如果idx1小于数组1的长度，说明数组1还没遍历完毕 if(idx1<len1){ // 从数组1中取值 n1 = nums1[idx1]; } // 如果idx2小于数组2的长度，说明数组2也没遍历完毕 if(idx2<len2){ // 从数组2中取值 n2 = nums2[idx2]; } // 如果两个数组都能取值 if(n1!=null&&n2!=null){ // 比较两个值的大小，如果数组1取的值大于数组2取的值 if(n1>n2){ // 那么把小的放进合并数组中 megerArray[i] = n2; // 数组2的索引位向后移动，数组1的索引位不能动，还要参与下次比较 idx2++; }else{ // 如果数组1取的值小于等于数组2取的值，把小的放进合并数组中 megerArray[i] = n1; // 数组1的索引位向后移动，数组2的索引位不动，参与下次比较 idx1++; } }else if(n1!=null){ // 如果只有数组1能取值，说明数组2已经取值结束了 // 那么只需要逐个把数组1的值放进合并数组中即可 megerArray[i] = n1; idx1++; }else if(n2!=null){ // 如果只有数组2能取值，说明数组1已经取值结束 // 那么只需要逐个把数组2的值放进合并数组中即可 megerArray[i] = n2; idx2++; } } // 计算中位数； // 如果两个数组总长度是偶数，那么需要拿出中间的两个数来计算中位数； // 如果两个数组总长度是奇数，那么直接返回中间位置的数值即可； return total%2==0?(megerArray[mid]+megerArray[mid-1])/2.0:megerArray[mid]; } 复制代码
python实现
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: # 计算数组1的长度 len1 = len(nums1) # 计算数组2的长度 len2 = len(nums2) # 计算总长度 total = len1+len2; # 计算中间位置 mid = total//2 # 如果两个数组都是空 if total==0: # 直接返回0.0 return 0.0 # 如果数组1为空 if len1==0: # 如果只有1个元素，那么只返回这个数值 if mid==0: return nums2[mid] # 如果总长度是偶数，得找到中间两个数计算中位数 # 如果是奇数，那么直接返回中间位置的数值 return (nums2[mid]+nums2[mid-1])/2 if total%2==0 else nums2[mid] # 如果数组2为空 if len2==0: # 如果只有1个元素，那么只返回这个数值 if mid==0: return nums1[mid] # 如果总长度是偶数，得找到中间两个数计算中位数 # 如果是奇数，那么直接返回中间位置的数值 return (nums1[mid]+nums1[mid-1])/2 if total%2==0 else nums1[mid] # 下面开始合并排序 # 先创建一个空数组 megerArray = [] # 创建两个指针，分别指向数组1和数组2的起始位置 idx1 = 0 idx2 = 0 # 合并排序 for i in range(mid+1): # 初始化两个值为None，以便后续判断是否从数组中取值 n1 = None n2 = None # 如果idx1小于数组1的长度，说明数组1可以取值 if idx1<len1: # 从数组1中取值 n1 = nums1[idx1] # 如果idx2小于数组2的长度，说明数组2可以取值 if idx2<len2: # 从数组2中取值 n2 = nums2[idx2] # 如果取的值都不为空，说明两个数组都取值成功 if n1 is not None and n2 is not None: # 比较两个数的大小； # 如果数组1取的值大于数组2中取的值，那么把小的值先放进合并数组中，数组2对应的索引位向后移动 if n1>n2: megerArray.append(n2) idx2+=1 else: # 如果数组1取的值小于等于数组2中取的值，那么把小的值先放进合并数组中，数组1对应的索引位向后移动 megerArray.append(n1) idx1+=1 # 如果只有数组1取到了值 elif n1 is not None: # 那么把取到的值放进合并数组中，数组1的索引位向后移动 megerArray.append(n1) idx1+=1 # 如果只有数组2取到了值 elif n2 is not None: # 那么把取到的值放进合并数组中，数组2的索引位向后移动 megerArray.append(n2) idx2+=1 # 当全部合并完成后，我们开始计算中位数 # 当总长度是偶数时，取出中间索引位置的两个数值计算中位数； # 当总长度时奇数时，直接取出中间索引位置 return (megerArray[mid]+megerArray[mid-1])/2 if total%2==0 else megerArray[mid] 复制代码
rust实现
pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 { // 计算数组1的长度 let len1 = nums1.len(); // 计算数组2的长度 let len2 = nums2.len(); // 计算总长度 let total = len1 + len2; // 计算中间位置 let mid = total / 2; // 如果两个数组都为空 if total == 0 { // 返回0.0 return 0.0; } // 如果数组1为空 if len1 == 0 { // 如果数组2只有一个元素，直接返回 if mid == 0 { return nums2[mid] as f64; } // 如果总长度为偶数 if total % 2 == 0 { // 拿出中间位置两个元素计算中位数 return (nums2[mid] + nums2[mid - 1]) as f64 / 2 as f64; } // 如果是奇数，直接返回中间位置元素 return nums2[mid] as f64; } // 如果数组2为空 if len2 == 0 { // 如果数组1只有一个元素，直接返回 if mid == 0 { return nums1[mid] as f64; } // 如果总长度为偶数 if total % 2 == 0 { // 拿出中间位置两个元素计算中位数 return (nums1[mid] + nums1[mid - 1]) as f64/ 2 as f64; } // 如果是奇数，直接返回中间位置元素 return nums1[mid] as f64; } // 创建一个合并数组 let mut meger_array: Vec<i32> = vec![]; // 创建两个指针分别指向数组1和数组2的起始位置 let mut idx1 = 0; let mut idx2 = 0; // 循环合并排序 for i in 0..mid+1 { // 创建两个Option类型数据，分别代表从数组1和数组2中取出来的值 let mut n1 = None; let mut n2 = None; // 如果idx1小于数组1的长度，那么说明数组1可以取值 if idx1 < len1 { // 从数组1中取值 n1 = Some(nums1[idx1]); } // 如果idx2小于数组2的长度，那么说明数组2可以取值 if idx2 < len2 { // 从数组2中取值 n2 = Some(nums2[idx2]); } // 如果从数组1和数组2中取的值都不为空 if n1.is_some() && n2.is_some() { // 比较两个值，小的先存进合并数组中 // 如果数组1中取的值大于数组2中取的值 if n1.gt(&n2) { // 数组2中取的值添加到合并数组中 meger_array.push(n2.unwrap()); // 并移动数组2的指针 idx2 += 1; } else { // 数组1中取的值添加到合并数组中 meger_array.push(n1.unwrap()); // 并移动数组1的指针 idx1 += 1; } } else if n1.is_some() { // 如果数组1中取的值不为空，说明数组2遍历完毕 // 那么直接把数组1取的值添加到合并数组中 meger_array.push(n1.unwrap()); // 移动数组1的指针 idx1 += 1; } else { // 如果数组2中取的值不为空，说明数组1遍历完毕 // 那么直接把数组2取的值添加到合并数组中 meger_array.push(n2.unwrap()); // 移动数组2的指针 idx2 += 1; } } // 合并排序到中间位置后，已经足够计算中位数了 // 判断总长度是偶数 if total % 2 == 0 { // 取出中间两个数计算中位数 return (meger_array[mid] + meger_array[mid - 1]) as f64 / 2 as f64; } // 如果是奇数，直接返回中间位置元素 return meger_array[mid] as f64;
