题目描述
给定两个大小分别为 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
示例 3:
输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000
示例 4:
输入:nums1 = [], nums2 = [1]
输出:1.00000
示例 5:
输入:nums1 = [2], nums2 = []
输出:2.00000
提示:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
进阶:你能设计一个时间复杂度为 O(log (m+n))
的算法解决此问题吗?
代码
1 /* 2 * @lc app=leetcode.cn id=4 lang=cpp 3 * 4 * [4] 寻找两个正序数组的中位数 5 */ 6 7 // @lc code=start 8 //#include<vector> 9 class Solution { 10 public: 11 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 12 int i = 0, j = 0; 13 int len1 = nums1.size(),len2 = nums2.size(); 14 vector<int> nums; 15 if(nums1.empty()) 16 { 17 while(j <= nums2.size() - 1) 18 { 19 nums.push_back(nums2[j]); 20 j++; 21 } 22 j--; 23 if(j % 2 == 0) return nums[j / 2] * 1.0; 24 else return (nums[j / 2] + nums[(j + 1) / 2]) * 1.0 / 2; 25 } 26 if(nums2.empty()) 27 { 28 while(i <= nums1.size() - 1) 29 { 30 nums.push_back(nums1[i]); 31 i++; 32 } 33 i--; 34 if(i % 2 == 0) return nums[i / 2] * 1.0; 35 else return (nums[i / 2] + nums[(i + 1) / 2]) * 1.0 / 2; 36 } 37 while(i <= nums1.size() - 1 && j <= nums2.size() - 1) 38 { 39 if(nums1[i] <= nums2[j]) 40 { 41 nums.push_back(nums1[i]); 42 i++; 43 } 44 else 45 { 46 nums.push_back(nums2[j]); 47 j++; 48 } 49 } 50 while(i <= nums1.size() - 1) 51 { 52 nums.push_back(nums1[i]); 53 i++; 54 } 55 while(j <= nums2.size() - 1) 56 { 57 nums.push_back(nums2[j]); 58 j++; 59 } 60 i--; 61 j--; 62 //printf("%d %d",i,j); 63 64 if((i + j) % 2 != 0) return nums[(i + j) / 2 + 1] * 1.0; 65 else return (nums[(i + j) / 2] + nums[(i + j) / 2 + 1]) * 1.0 / 2; 66 67 68 } 69 }; 70 // @lc code=end