公众号merlinsea
- 题目连接
- 题目描述
- 给定两个大小分别为
m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的 中位数 。
- 示例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
- 思路1
- 把两个数组从小到大进行合并，合并成为一个数组以后选择中间的结果输出。由于题目给出的两个数组都保证了两个数组是从小到大的，因此我们可以每次用两个数组最小的元素比较，哪个小哪个就放前面。
- 时间复杂度收O(m+n),空间复杂度是O(m+n)
class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { vector<int> arr; int i = 0; int j = 0; while(i<nums1.size() && j<nums2.size()){ if(nums1[i]<nums2[j]){ arr.push_back(nums1[i]); i++; }else{ arr.push_back(nums2[j]); j++; } } while( i<nums1.size()){ arr.push_back(nums1[i]); i++; } while(j<nums2.size()){ arr.push_back(nums2[j]); j++; } // 保证 arr是有序的 // 如果长度为奇数， 0 1 2 3 int mid = arr.size()/2; if(arr.size()/2 == 1){ return arr[mid]; }else{ double res = (arr[mid]+arr[mid-1])/2.0; return res; } } };
- 思路2
- 参考找位置的思路，比如在一个总长度为2n的有序序列中，我们需要返回第n个和第n+1个元素的平均值即可；对于长度为2n+1的有序序列中，我们需要返回第n+1个位置的元素即可，因此我们可以发现寻找中位数其核心是寻找第k个位置的元素。
- 在寻找第k个位置的元素的问题中，现在题目给了我们两个长度分别为m和n的有序序列，可以考虑先排除前k/2个元素，比如我们首先在长度为m的序列中找到第k/2个元素a，然后在长度为n的序列中也找到第k/2个元素b，假设a<b，则说明在长度为m的序列中前k/2个元素一定不是我们要寻找的元素（故可以排除），因此接下来我们只需要在长度为m-k/2的有序序列和长度为n的有序序列中找合并以后的排在第k/2个元素即可。
- 时间复杂度是log(m+n),空间复杂度是log(max(m,n))
class Solution { public: /* 解题思路： 寻找第k大大数组 */ double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int len1 = nums1.size(); int len2 = nums2.size(); int left = (len1+len2+1)/2; int right = (len1+len2+2)/2; int mid1 = find(nums1,0,nums2,0,left); int mid2 = find(nums1,0,nums2,0,right); return (mid1+mid2)/2.0; } int find(vector<int> &nums1,int i,vector<int> &nums2,int j,int k){ if(i>=nums1.size()){ //说明nums1是空数组 return nums2[j+k-1]; } if(j>=nums2.size()){ //说明num2为空 return nums1[i+k-1]; } //当k==1的时候，显然k/2 = 0 这在本题中没有意义 if(k==1){ return min(nums1[i],nums2[j]); } //每个数组前k/2位置的元素 //为什么在数组不足k/2个元素时候需要将val1要设置为INT_MAX ？ 重点 //为什么需要每次找k/2个元素！！ int val1 = INT_MAX; if(i+k/2-1<nums1.size()){ val1 = nums1[i+k/2-1]; } int val2 = INT_MAX; if(j+k/2-1<nums2.size()){ val2 = nums2[j+k/2-1]; } if(val1 < val2){ return find(nums1,i+k/2,nums2,j,k-k/2); }else{ return find(nums1,i,nums2,j+k/2,k-k/2); } } };
算法训练营永久班上课开始啦，欢迎大家积极报名～
奔跑的小梁，公众号：梁霖编程工具库算法训练营春节价格通知,2023年2月12日
