Leetcode题目总结[4]寻找两个正序数组的中位数

题目描述

给定两个大小分别为 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

 

Leetcode题目总结[4]寻找两个正序数组的中位数

上一篇:Visual Studio 2013 新增web项目IIS Express的64位版


下一篇:.Net高级技术——程序集