给定两个大小分别为 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
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
直接合并后计算中位数即可
1 class Solution { 2 public: 3 4 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 5 6 vector<double> merge; //合并后数组 7 int j=0; 8 int m=nums1.size(); 9 int n=nums2.size(); 10 nums2.push_back(-1); 11 //合并 12 for (int i=0;i<m;++i){ //完整遍历nums1,把nums2中比nums1小的数插入 13 while (nums1[i]>nums2[j]){ //把从nums2[j]开始小于nums[i]的数都插入merge数组中 14 if (j<n){ 15 merge.push_back(nums2[j]); 16 ++j; 17 } 18 else 19 break; 20 } 21 merge.push_back(nums1[i]); 22 } 23 for (;j<n;++j){ //把num2中剩下比num1大的数插入 24 merge.push_back(nums2[j]); 25 } 26 //合并完成后直接计算中位数 27 if ((n+m)%2==0) 28 return (merge[(n+m)/2-1]+merge[(n+m)/2])/2; 29 else 30 return merge[(n+m)/2]; 31 32 } 33 };
标签:正序,int,中位数,力扣,数组,nums1,nums2 From: https://www.cnblogs.com/coderhrz/p/17080734.html